*These are just my opinions, and I might have missed something, so if you disagree with me, or you have a suggestion, I will take them into consideration*

I've had *a bit* of free time lately, and I spent *a bit* of that looking up 4th gen. battles. The most used Pokemon I saw were Swampert, Heatran, Tyranitar, and Scizor, closely followed by Jirachi, Azelf and Flygon... I'm no genius, but of those Pokemon, all of them except our favorite Smurf are part Rock, Ground or Steel. This means a prevalence of Sandstorm, as you can probably tell by Tyranitar's Sand Stream ability. Now, I've played a bit with weather teams, and I set them up the following way:

Lead - Revenge Killer - Sweeper - Phys Wall - Spec Wall - Counter

So, here is a guide to building a Sandstorm team in 4th gen. This means that I will not cover Pokemon or sets like Toxic Heal Gliscor, Terrakion, or even Garchomp (because it was Uber), but I'll give sets for all the main Threats you can use in a Sandstorm team, and what to be worried about. This isn't a definitive guide, it is a starting off point for any of you wanting to try Sandstorm. I'm going to give a list of Pokemon, and the sets, for each role.

------->Lead:<-------

There are two things that a Sandstorm lead might want to do; activate Sand Steam with Hippowdon or Tyranitar, or set up SRocks. The only Pokemon who can set up SRocks in these kinds of teams are Hippowdon, Tyranitar, Aerodactyl and Swampert. Lead Jirachi isn't as good in 4th gen, and the other SR users don't have much use outside of entry hazards, because of the fact that they won't synergize well with the rest of the team. Anti leads might work, I guess, but I don't think they work as well. Here are the best lead Pokemon:

Hippowdon @ Leftovers
Impish - Sand Stream - 252 HP/252 Def/4 Spe
~Earthquake
~Slack Off
~Stealth Rocks
~Roar/Toxic
Hippowdon has good defenses and less weaknesses than Tyranitar, with access to Stealth Rocks, Slack Off and Toxic/Roar, he is a good setup lead, as well as Physical Wall, which means you can afford to have a second Sweeper or Support.

Swampert @ Leftovers
Relaxed - Torrent - 252 HP/152 Def/100 SpDef/4 Spe
~Stealth Rocks
~Earthquake
~Ice Beam/Waterfall
~Roar
U liek dem Mudkipz? Swampert is used a LOT in OU. Ice Beam gives great coverage with Earthquake, while Waterfall gives another powerful STAB move. Using a Swampert will let you use a DD Tyranitar as a second sweeper. The minimal Speed investment will let you outspeed other Swampert, who are very common. If you go for Waterfall, you should go for an Impish nature over a Relaxed.

Aerodactyl @ Focus Sash
Jolly - Pressure - 252 HP/4 Atk/252 Spe
~Stealth Rock
~Taunt
~Earthquake
~Stone Edge
Aerodactyl is the fastest non-Scarfed Stealth Rock user in OU. Taunt on the first turn, if you predict Status or entry hazards, and Stealth Rock on the second. Quake/Edge makes for a good offensive combo, but it is mostly a suicide lead. He is great for consistent setup, but not the best lead on this list.

Tyranitar @ Focus Sash
Jolly - Sand Stream - 252 HP/4 Atk/252 Spe
~Stealth Rock
~Crunch/Pursuit
~Stone Edge
~Earthquake
Lead Tyranitar, at least to one I have here, is a Sand Stream user who can setup Stealth Rocks fairly consistently, but it is a waste of a Tyranitar. I think that this set can work, but if you don't need Stealth Rocks for your team to work it's magic, go for another Tyranitar set, even if you lead off with it.

Other Options: Heatran - Forretress - Metagross - Skarmory

------->Revenge Killer:<-------

There are a few revenge killers in 4th gen, and most of them work in Sandstorm. There are a few Pursuit trappers, like Tyranitar, but there are two Pokemon that can easily KO other Pokemon with switch advantage. Dugtrio has the fantastic ability Arena Trap, which prevents the opponent from switching out. Scizor is the other revenge killer, who has access to Bullet Punch and Pursuit. Both should be Choice Banded, because speed is not an issue, and you don't need to worry about counters coming in. Here are the two revenge killing sets:

Dugtrio @ Choice Band
Jolly - Arena Trap - 4 HP/252 Atk/252 Spe
~Earthquake
~Stone Edge
~Night Slash
~Aerial Ace
With Arena Trap, he is a natural Revenge Killer and can OHKO common threats like Heatran with ease (even the ones with Shuca Berry). With a positive nature and 120 base speed, Dugtrio doesn't need any bulk whatsoever.

Scizor @ Choice Band
Adamant - Technician - 248 HP/252 Atk/8 Spe
~Bullet Punch
~Pursuit
~U-Turn
~Superpower
Classic Scizor is still an upper-OU Pokemon in wifi battling today, meaning it must have been really good back in HGSS era. The set hasn't changed a bit, and the environment is friendlier to it. Having a Heatran on your team will let you absorb fire moves that take out Scizor with ease. Bullet Punch if you predict the opponent to stay in, Pursuit if you think you will kill, and they will switch out and U-Turn if you just want damage and a free switch. Superpower is the only move with over 60 base power, meaning Technician is a LOT better than Swarm on this thing. Another option is to go for an SD variant and setup when you scare out your opponent. The 8 Speed EVs let you outspeed the common 252/252/4 set without losing power or much bulk.

Other Options: Heatran - Tyranitar - Magnezone

------->Sweeper:<-------

The sweeper's goal is to KO the opponent's team once it's counter's have been eliminated. With Sandstorm teams, there are a few sweepers that are used a lot, and for good reason. I'm only going to post the three that I think work best here, but again, this is just a starting off point. Two of the sets here are Scarfed, and this isn't great as a team's only offensive force, but most people have more than one offensive Pokemon on a team. While I said that a team structure only has one, the counter also fills an offensive role, and a defensive lead can allow a second sweeper. Here they are:

Tyranitar @ Choice Scarf
Jolly - Sand Stream - 4 HP/252 Atk/252 Spe
~Stone Edge
~Crunch
~Earthquake
~Superpower
Tyranitar has Sand Stream, so this set is almost a must if you don't have one of it's variants, or a Hippowdon in the lead slot, this is a must for sand teams. Tyranitar is a prime candidate for a Scarf, as it has 61 base speed. Where most OU Pokemon have a base Speed stat that is a multiple of 5, this extra point really sticks out well. I highly recommend this if you have a Swampert or Aerodactyl lead.

Flygon @ Choice Scarf
Jolly - Levitate - 4 HP/252 Atk/252 Spe
~Earthquake
~Outrage
~Fire Blast/Stone Edge
~U-Turn
Flygon is one of a few dragon types in OU, and he has very key immunities (ground and electric) along with good offensive stats. With a scarf, Flygon also makes a good scout, with U-Turn helping it out quite a bit. There are other sets, but this one is most standard, and is quite effective.

Heatran @ Life Orb
Timid - Flash Fire - 4 HP/252 SpAtk/252 Spe
~Fire Blast
~Earth Power
~Explosion
~Metal Sound/HP Grass
*Note: Heatran can fill most roles on this team, and although I will not be listing them all, you can check Smogon if you want to find them. I will be showing the SpDef set later in this guide, but if you want to find it's trapping, lead or Choice sets, Smogon is the place for you*
Heatran in this context is a special attacker who is not as good as the Pokemon above, but can be used if you don't like locking yourself into one move.
HP Grass is for taking out ground types, while Metal Sound is used to break walls and force switches. Blissey can be KO'ed with the Metal Sound variant, or through Explosion, but the Metal Sound way is preferable.

Tyranitar @ Life Orb/Lum Berry
Jolly - Sand Stream - 4 HP/252 Atk/252 Spe
~Dragon Dance
~Stone Edge
~Crunch
~Earthquake/Aqua Tail
I can't believe I missed this set when I first made the guide (added this on 25/2/13), but this is a great set that is quite common. DD Tyranitar is one of the biggest threats in DPP OU, and for good reason. First, it lays down Sandstorm that deals residual damage that takes out Sash users, and second it provides fantastic power, even if you aren't able to set up. With speed maxed out on positive, it will outspeed (unboosted) all non-scarfed Empoleon, Magnezone and Swampert, and can OHKO the former two with Earthquake.

Lucario @ Life Orb
Adamant - Inner Focus - 4 HP/252 Atk/252 Spe
~Swords Dance/Agility
~Close Combat
~Extremespeed
~Crunch
While Lucario doesn't benefit from Sandstorm, he isn't damaged, and so is a good option. Swords Dance is the more common variant, but Agility works as well. The strategy here is to get a boost on a forced switch, and then go for a sweep. Extremespeed is the move you will be spamming the most, but your other moves are good too. You can replace Crunch with Ice Punch, but I would recommend Crunch more.

Other Options: Metagross - Gliscor - Empoleon

------->Physical Wall:<-------

The physical wall can take hits and wear down opponents. Forretress isn't ideal, because of the lack of recovery and x4 fire weakness, but provides hazard support. I can recommend Skarmory a bit more, as it has two weaknesses, one of which is walled by ground types, a reliable recovery move, and phazing capabilities. Gliscor is the only good non steel type physical wall of these three. You can skip out on a physical wall if you have a Hippowdon lead, or maybe even a Swampert.

Skarmory @ Leftovers
Impish - Keen Eye - 252 HP/252 Def/4 SpDef
~Roost
~Whirlwind
~Stealth Rocks/Spikes
~Air Slash
Skarmory is great when paired with a Pokemon like Swampert, as they cover each other's weaknesses. Spikes should be taken if you're lead has Stealth Rocks. It is one of the best Physical walls in the game, with instant recovery and 140 base Defense, and good phazing capabilities.

Gliscor @ Leftovers
Impish - Sand Veil - 252 HP/252 Def/4 Spe
~Roost
~Earthquake
~Toxic
~Taunt
While Gliscor doesn't have Toxic Heal yet, it has two key immunities and high Defense. Taunt and Roost combined with it's 125 base defense make it an effective wall, and Toxic can be used to wear down the opponent while Earthquake hurts them. The ice weakness is easily covered by steel types on the team, and the water weakness is a downside, but it isn't too bad. Sand Veil isn't banned this gen!

Forretress @ Leftovers
Relaxed - Sturdy - 252 HP/252 Def/4 SpDef
~Rapid Spin
~Explosion
~Spikes
~Toxic
Forretress isn't the best wall, because of a lack of recovery, and it should never be on the same team as Scizor, but Forretress is a solid wall that can stall out opponents with Toxic, spin away hazards and set up Spikes.

Other Options: Metagross - Bronzong - Hippowdon

------->Special Wall:<-------

There are really only two special walls that are compatible with Sandstorm, and one of them is only a 100/90/90 bulky lead, Swampert. This leaves Heatran, who can run a very effective set. There might be Special Walls that I'm missing, but this is all I found that can work.

Heatran @ Shuca Berry
Calm - Flash Fire - 252 HP/4 SpAtk/252 SpDef
~Lava Plume
~Earth Power
~Roar
~Protect
*Note: Heatran can fill most roles on this team, and although I will not be listing them all, you can check Smogon if you want to find them. I will be showing the Offensive set earlier in this guide, but if you want to find it's trapping, lead or Choice sets, Smogon is the place for you*
This Heatran is defensive, and I can recommend it quite a bit for the sole reason that there are very few other Special Walls that are compatible with Sandstorm. The other great thing about this is that it has flash fire, allowing you to take a Scizor without much risk. Shuca Berry reduces the power of Ground type moves, so it might be able to live another Heatran's Earth Power before firing back with it's own.

Other Options: Swampert


------->Counter:<-------

Here is a list of types that are super effective against Steel, Rock and Ground types:
Water - Grass - Ice - Fire - Fighting - Ground - Steel
Heatran, entry hazards and Ground types take care of Fire types, Steel takes care of Ice and Grass is taken care of by Heatran and they aren't seen too much anyways. Now the main types that can be a problem to Sandstorm teams are Water, Fighting and Ground. Steel types are countered by ground, so that isn't much of an issue either. The job of the counter is to eliminate these counters so you can do your thing. There are many counters that you can use, but you need to tailor it to your team. Depending on your other five pokemon, Ground might not be an issue, or whatever the case may be. This is probably the best counter though, who can deal with all three of these types:

Celebi @ Leftovers
Timid - Natural Cure - 220 HP/252 SpAtk/36 Spe
~Leaf Storm
~Psychic
~Recover
~Leech Seed
Celebi is not the best Pokemon in 4th gen., but it can easily take out all three types, if that is what you need. The leftovers negate the damage it will be taking from Sandstorm, and it is pretty strong. This set is fairly bulky, with Natural Cure and 220 HP EVs. If any of the three types above are already countered, this might not be your best bet, but this is the most average counter.

Zapdos @ Leftovers
Bold - Pressure - 248 HP/228 Def/32 Spe
~Thunderbolt
~Heat Wave
~Roost
~Roar
Defensive Zapdos is a powerful counter here, as it resists Fighting, is immune to Ground unless he is roosting, and has TBolt for water types. This Zapdos is very powerful, and can even take the place of a Physical Wall, allowing another Sweeper. Zapdos doesn't resist Water, but counters all three types that wreak havoc on Sandstorm teams. A specially defensive variant will let you skip out on s Special Wall, meaning you can use Heatran in another role.

Other Options: Starmie - Shaymin

------->Example Team:<-------

Swampert @ Leftovers
Relaxed - Torrent - 252 HP/152 Def/100 SpDef/4 Spe
~Stealth Rocks
~Earthquake
~Ice Beam
~Roar

Scizor @ Choice Band
Adamant - Technician - 248 HP/252 Atk/8 Spe
~Bullet Punch
~Pursuit
~U-Turn
~Superpower

Tyranitar @ Lum Berry
Jolly - Sand Stream - 4 HP/252 Atk/252 Spe
~Dragon Dance
~Stone Edge
~Crunch
~Earthquake

Flygon @ Choice Scarf
Jolly - Levitate - 4 HP/252 Atk/252 Spe
~Earthquake
~Outrage
~Fire Blast
~U-Turn

Heatran @ Shuca Berry
Calm - Flash Fire - 252 HP/4 SpAtk/252 SpDef
~Lava Plume
~Earth Power
~Roar
~Protect

Zapdos @ Leftovers
Bold - Pressure - 248 HP/228 Def/32 Spe
~Thunderbolt
~Heat Wave
~Roost
~Roar

*feel free to leave any sandstorm teams that you've made in this thread*