There is no wrong way to eat a Reese's, right? With the Shaman being a hybrid class, there is no wrong spec for them. There are, however, two wrong specs to level as. If you take a look at the loot itemization early on in the game, you'll notice there isn't a lot of caster leather pre-40, nor caster mail post-40 until the late 50's or Outlands. This eliminates Restoration and Elemental as faster specs.
The key to getting your Shammy to 70 as fast as possible is to level Enhancement. I cannot stress this enough. There is a ton of Rogue gear to roll on until you hit mail at 40. At that point, the pieces in Scarlet Monestary will last you until Outlands.. yes.. that long. If you have a main with a few high level enchanting mats, it's worth it to throw on some +STR or +AP enchants to that gear.
The first thing is to not get discouraged early on in the game. You'll be using a 1h + shield until level 20 when you can finally equip a 2h so those are going to be the slowest levels for you. At 20 you want to focus on getting the best 2h Axe or Mace possible and keeping Flametongue weapon on it at all times. The most depressing news is that you do not get Windfury for quite some time so you'll be using Flametongue in it's place until then.
At 40, Dual Weilding becomes available and makes life much easier for you. Pop Windfury on both and go to town.
Before we get a bit more in-depth, lets discuss the races available for Shaman.
Your choice is simple if you plan on rolling Alliance since the Draenei are the only option. Their Gift of the Naaru racial is nice when you're out of mana or in a pinch. It also comes in handy to toss on yourself before pulling multiple mobs.
As a Hordie, you can pick from the Orcs, Trolls and Tauren. The Tauren have War Stomp which is great when you need to pop a quick heal or stop another player from casting in PVP. The Trolls Berserking works great, especially as an Elemental Shaman. The Orc's Bloodrage is a bit too situational for me but still comes in handy. My choice? Troll.
How about professions?
This really depends on how you want to spec your Shaman at 70. If you're in to making your own gear, you can't go wrong with Blacksmithing or Leatherworking (Dragonscale). If you're planning to level and stay Enhancement, Blacksmithing can provide some amazing weapons to deal out DPS. Shaman cannot use swords so going Swordsmithing is out of the question but there are some great 1h maces (i.e. Dragonstrike) that are Black Temple quality. Leatherworking will provide you with some great gear later on and you'll want to go with the Dragonscale specialization. This allows you to create mail gear that fits Elemental and Enhancement pretty well but not so much Restoration. If you're going Restoration I might suggest something like Engineering or Alchemy instead. As always, First Aid is important regardless of class.
Lets look at gear priority.
Since you'll be leveling as Enhancement, you'll want to focus on +STR and +STA gear. STR gives us +AP and scales better than raw +AP gear. STA is important since you'll be soloing as a melee class because you'll be taking a beating. AGI is more a Rogue stat. The common misconception is that Shaman need AGI for the crit % but that only helps our "white damage" crits. Unlike a Rogue or Fury Warrior, white damage is only about 30-40% of our DPS. The rest comes from Windfury and Shock damage which aren't effected by our crit rating.
While you're stuck with a 2h weapon from 20-40 you'll want to aim for about a 3.0 speed. Anything faster is going to lower your DPS but anything higher is for Warriors and Ret Paladins. They have attacks that work off of weapon damage where Shaman do not. 3.0 is the perfect speed because it'll do a decent amount of DPS and you'll have your Flametongue Weapon effect proccing each hit. Once you get Windfury, it has a 3 second internal cooldown so anything faster than 3.0 lowers you chance to proc per swing.
Once you start to dual-weild, stay away from fast weapons. You want both weapons to be at 2.6 speed or slower. This doesn't blow the Windfury internal cooldown as often and deals more damage with Windfury when it procs. Some people use Flametongue on the off-hand since off-hand has a higher miss rate and deals less damage than the main-hand by default. The reasoning behind this is to not waste a Windfury cooldown on a weaker off-hand hit. If you have a faster off-hand weapon than 2.6, I'd always use Flametongue Weapon over Windfury on that weapon to make up for lost DPS. If both weapons are 2.6 or slower, having Windfury on both will increase your DPS.
Shock it to me?
As you level, you'll eventually learn Earth Shock, Flame Shock and Frost Shock. Each serves it's own purpose and should be used in your combat rotation.
Earth Shock - ES deals burst damage and interrupts spell casting. Since it is nature damage, the damage is increased if the Stormstrike debuff is on the target. My advice is to have Rank 1 and your max rank on your bar. If you just need to interrupt a spell cast, Rank 1 does the same thing that the max rank does. Only use the max rank for DPS purposes.
Flame Shock - Flame Shock works like a Warlock's Immolate spell where it deals intial burst damage followed by damage over time. This is the highest DPS shock for a Shaman and is very underestimated. I also recommend having Rank 1 on your bar if you PVP. Hitting a Rogue with a Rank 1 shock will remove their ability to Vanish.
Frost Shock - Frost Shock deals burst damage and adds a slowing effect to the target. The downfall of this shock is that it also deals additional threat, so avoid using anything over Rank 1 in dungeons or you'll wind up tanking the mob. At first, this will deal more damage than Earth Shock but in the end (at 70) Earth Shock will beat it at.
Your shock rotation should be Flame Shock -> Earth Shock when cooldown is over, repeat. Always start with Flame Shock to let it's DoT deal it's damage while piling on Earth Shock as well.
How bout dem totemz?
At first, totems will become a bit overwhelming. You'll get a ton of them very early and I recommend downloading a totem mod to keep track of them for you. I prefer YATA but some people prefer Chaman. Totems are broken down in to 4 categories - Earth, Air, Fire and Water. Only one totem from each element can be dropped at a time. Any totems dropped afterwards will replace the previous one of the same element.
For example - If you drop Strength of Earth and then drop a Tremor Totem, the Tremor Totem will replace the Strength of Earth since both are "earth totems".
Honestly, you'll waste a lot of mana dropping one of each totem. Most are better set for group settings but for soloing I'd only use Strength of Earth and Grace of Air totems. You won't get Grace of Air until after 30 I believe. It's also a good idea to set yourself in the middle of the mobs you'll be killing, dropping your totems and then pulling the mobs to you. If this is the case, feel free to drop a Mana Spring totem as well. If you're going to be killing and moving, Mana Spring will cost more mana than you'll receive in return and will be a waste.
SPECS! SHOW ME SPECS!
The first 5 points don't give you many options. Shield Spec is useless so go 5/5 Ancestral Knowledge for +5% mana. The next 5 should go in to Thundering Strikes to increase your melee crit chance by 5%. Both of these are very self explainitory.
The next point goes in to the new Ancestral Focus which gives you a mana reduction on your next shock whenever you land a critical melee attack. Since shocks are a huge part of your DPS, this is a great idea. Toss the next 2 points in to Enhancing Totems for a 16% boost to Strength of Earth and the drop the final 2 points up in to Improved Ghost Wolf making it an instant cast. Some people laugh at this but it's a great GTFO button and gets you from point A to point B faster.
Tier 4 should have 5/5 Flurry to boost attack speed by 30% whenever you land a melee crit. This is huge when you're stuck using a 2h weapon.
When you reach the Tier 5 level, put the first point in to Spirit Weapons. This is the only way to get Dual Weilding. This is also the only way for Shaman to learn "parry" and it's threat reduction helps a lot in dungeons. Pop 3 points in to Elemental Weapons to increase the damage bonus to your Flametongue and Windfury effect. This is also the only way to learn Stormstrike which will be a great addition to your combat rotation. Now you're stuck with 1 point to throw somewhere to hit Tier 6. My advice is just to throw it in to Improved Lightning Shield to help kill a bit faster or to put a point in Anticipation for +1% to dodge.
Put all 5 points in to Weapon Mastery to increase your overall melee dps. Tier 6 is pretty self explainitory.
Once you ding 40 you have a choice to make. Dual Weilding or Storm Strike first? Personally, I'd go for dual-weilding and pick up Stormstrike at 41. Stormstrike attacks with both weapons dealing their exact weapon damage and applies a debuff which increases the amount of nature damage the target receives by the next 2 sources. This is the reason you want 2.6 speed 1h weapons. Drop the last 3 points in to Dual Weild Specialization for a quick +6% chance to hit in melee.
5/5 Unleashed Rage for Tier 8 and 1/1 Shamanistic Rage for Tier 9 is what you're aiming for.
There is really nothing more to spend points on with Enhancement so you'll want to move over to the Restoration tree from here on out. Rather than give you an order to pick from, here are the talents to place points in and you can decide which are more important to you. Personally, i'd get down to Healing Focus as fast as possible and put 5 points in that. That and 3/3 Natures Guidance are the only reasons to really be in Restoration.
5/5 Improved Healing Wave
2/2 Improved Reincarnation
4/5 Totemic Focus
1/1 Totemic Mastery
5/5 Healing Focus
3/3 Natures Guidance
Thats pretty much the jest of it. One you get in to Resto it's just icing on the cake. You have all the tools you need from Enhance to breeze your way to 70. Just keep Lightning Shield up, drop Strength of Earth & Grace of Air totems, keep Windfury on your weapon and unleash the Shamanistic Fury.