This hasn't been an active thread for quite some time, but I'm going to comment on this anyway (and hopefully spark some sort of discussion =/).
Almost anything worth using can potentially use a Substitute set. It may not be optimal, but the possibility is there. Even things like Amoonguss can opt for Substitute over Protect in order to make Trick Room teams cry all that much harder. So I'm not going to bother posting sets (if ur dying to know some Sub users I use a lot as of lately include Chandelure, Kyurem-B, and Terrakion; I haven't actually been using it as much lately believe it or not).
Regardless, I personally thing a good few players overuse it to an extent (am looking at Laga). Not to say it isn't a great move, but you should at the least be considering whether Eruption is a better pick than Substitute on your Heatran for a given team rather than slapping it on mindlessly.
Still, why is Substitute so good? Its definitely not SubProtect + Lefties stalling (sorry youngjake), 12.5% recovery would hardly be worth it on its own.
One of the big reasons is because Substitute punishes switches incredibly flexibly. You don't have to bother guessing what will come in, you can just Sub up and use whatever move deals with the switch in more effectively (a common technique on Sub Garchomp, for instance). This makes Substitute a very "safe" move in a lot of situations, though in others it can be really risky (for instance if you have Sub Heatran in front of two threatening opponents such as Landorus-T and Conkeldurr, you will either have to switch out which tends to be a fairly risky play or properly use Protect as if you do not you'll be forced to switch or quite possibly be knocked out the following turn). Additionally, it expands the time you can stall allowing a partner to get rid of checks and counters (this is what I expect youngjake was getting at). This is probably what makes Heatran so annoying, as due to the fact it walls so many things and generally is countered by a mere Pokemon or two on the opposing team, luring out Landorus-T and then allowing a Rotom-W to beat it or force it back out is great for keeping the momentum in your favor (the fact it helps keep momentum going is why it is as Laga said overall more effective on offensively orientated Pokemon). And of course it blocks status moves, which has definitely become a larger factor since sleep clause is now gone, as blocking Spores is a great help to a lot of Pokemon. Overall I'd say the biggest reason Substitute is so useful is the fact it buys you time. Whether its more time to scout, more time to eliminate counters, or more time to attack things, an extra turn goes a long way in Doubles.
I'll also address mind games that occur around Substitute. I think most of us can agree that when something gets a Substitute up our first thought is to double target the given Substitute user and get rid of it before it causes trouble. This is where I'll agree with youngjake that SubProtect is a good combination. You could try double targeting the given Pokemon, but if the person across the table calls that correctly and Protects, you've just wasted a turn. At the same time if they Protect and you call that and double target the other Pokemon, they are in a world of hurt as you quite possibly pick up a KO and double targetting the Sub user the following turn is a relatively safe play. I think a big concept at the center of playing against/with Substitute is the tempo, or basically the use of Protect, as since using Protect repeatedly is very risky, the moment you opt to use Protect (or whether you correctly call when Protect) will be extremely important.
So how do you beat Substitute? There are several ways. Some are commonly used while others I myself have never seen in a legitimate match.
Infiltrator
While you probably don't need me to tell you what this does, for those who aren't aware Infiltrator will allow you to bypass Substitutes. This makes Jumpluff a unique sleep inducer for instance, as Substitute (and Safeguard) cannot block its Sleep Powders. Chandelure is probably the most popular offensive Infiltrator users, though Noivern (and Crobat though its not as effective by far) is another effective choice.
Damaging Moves That Aren't Blocked
Needless to say, I learned about this one the hard way when Biosci thrashed my SubTran with a Snarlkou on the ladder. Any moves like Snarl will function similar to Infiltrator, bypassing the Substitute and dealing damage directly. Solid moves that aren't blocked include Snarl, Hyper Voice, Bug Buzz, and Boomburst (this one lacks any solid users unfortunately; needs more Refrigerate Aurorus :>).
Taunt
Stop Substitute before it goes up. Pretty direct strategy, though given the opposition only needs one turn to get it up I'd say its not as effective overall. Regardless, Thundurus is one of the best choices here.
Encore
Imo one the best anti-Substitute options, and the combination of it with Mega Gengar is probably why I am not using Substitute as frequently nowadays. If you switch Encore in on a Sub user or they for some reason Sub up in your face, you can simply lock them into Substitute. They can potentially stall a turn with Protect though after that they will either switch out or risk staying in. What Encore essentially does it make Substitute backfire, as while its a method to hold your momentum, Encore will steal that momentum and put you in a pretty tough spot, as you are forced to switch out (assuming you have been hit by Encore) allowing the opposition to nail a switch in or just focus their energy on the partner Pokemon (who will then face the same problems if it tries to Protect). In general Encore is a great move since it limits the opponent's options, but we're not talking about Encore, so let's move on.
Snatch
This is a sly little trick I've never actually seen used, but I'm mentioning it anyway. Essentially Substitute is one of many moves Snatch can snatch (some other useful moves it steals being Wide Guard, Quick Guard, and Tailwind). This allows you to steal the Substitute that a Heatran, for instance, would try to set up. I'd definitely judge it as a gimmick, though if you disagree feel free to prove me wrong.
Roar (and Whirlwind)
While not very common, this move has a lot of application. It bypasses Substitute and Protect, which allows it to put a halt to a lot of strictly speaking "gimmicky" set up strategies. That's about all there is to it, really.
Perish Song
Perish Trapping or simply using Perish Song by itself can really cause trouble to Sub users, as when their turns are numbered, buying time isn't exactly a valid strategy.
tl;dr Substitute is rubbishawesome, but please use it thoughtfully rather than mindlessly :s