Enh starts to be fun at 30, and IMO (sure you'll hear alternative opinions) is significantly easier to level than ele, provided you enjoy melee characters. Gear these days as you would a hunter, gear with agil, and intel (or ap/crit). Any guide that references strength for an ehn shammy is out of date. Get nice slow weaps if you can, but no so much that you totally ignore dps....and enjoy.

Enh really is very robust to level

"level 34 shaman, in quest greys"

Yikes! that's some crappy gear. ;)
(sorry, head to)

Don't know how fast you level, but i was going so quickly at that level that i just used quest rewards and sold what dropped on the AH. Getting to 58 on any character really makes a difference as the gear in outland will pretty much blow away any gear from old world. With all the changes to old world, with less mobs being elite, the quest stuff is decent for that level, and usually decent class stuff too. (this is all generally, i don't know much about shamans though for stats and such)

I have leveled 2 shamans, enhance(from way back when) and elemental fairly recently, elemental is far easier to lvl now than when it was, because they put in water shield at lower level's. At the time I was leveling elemental I was around lvl 34 I believe when the patch came out that gave him water shield at lower level, so I ended up training a couple ranks of it, but because of that elemental became a breeze to level with with zero downtime, I never ran out of mana! Enhance is fun, but not really until you get duel wield, and of course use the 2 hander now a days, when I leveled my enhance shammy you had to spec into 2 hander, so either should be fine now, just depends on your playstyle!

Oteo,

Shaman are very fun to level. I leveled as enhancement and dps'd / healed up to Brd. In Bc, I respec'd to Elemental, which gearing is basically same as Restro, and healed / dps'd through Lk. If I remember right int/crit for elemental/restro and str/agi for enhancement. As far as leveling, I'm sure that questhelper or Tomtom will work for you.Of course it is always best to pull up quests for a zone using Thottbot or similar and research what quests will provide you with the best gear for your level. Since you will not be able to complete all the quests for every zone why not target the ones that benefit your class/spec.

P.S. I leveled prior to dual spec, but you may want to spring for some mail heirlooms :)

First off use an updated button-bar add-on that supports the new totem bar. There are several available and you will be much happier. Second is make a totem macro with a castsequence to call your primary totem config and recall. Pop this macro to lay totems then when you need to move pop it again to recall. Very helpful. Just make sure to add a reset timer with the 5 min duration of your totems. Having your castsequence stuck on recall when you have no totems down is no fun at all.

As far as stats for Elemental: Hit > Spell Power > Haste > Crit

Intellect gets you a larger mana pool and more spell crit but this is only helpful if you are running out of mana and stopping to drink often. At any level gear with spellpower gear that comes with Intellect as most of it should. At level 80 all enhancement and resto gear comes with Intellect and Spell Power and there is no need to stack more intellect, through gems or enchants, than what comes with your gear. At lower levels hit gear is few and far between and does not matter at all when fighting mob at or below your level.

I have leveled an Enhancement Shaman to level 63 prior to WotLK's release and recently rolled and leveled an Elemental Shaman to 80 and geared through dungeons and raids. I really enjoyed the Enhancement Shaman's in-your-face all-out melee DPS smash-and-bash feel. Couple this with the ease of finding gear suited to the spec, shares gear with Hunters, and it was an easy and enjoyable leveling experience. My Elemental Shaman was leveled with the Mail Spell Power Heirloom shoulders, which you can only use starting at level 40 when you can start wearing mail. So the first 40 levels were made the old-fashioned way. This spec is fun to play especially if you do not enjoy melee and would rather burn your targets to the ground before they have a chance to go toe-to-toe with you.

Though both are Shaman and share spells and totems the play style between the 2 is so very different. I found both to be very enjoyable but I can see how the differences can lead a person to like or dislike a particular spec and is really a simple matter of personal preference. If you are planning to have a resto spec it may be best to have elemental as your other spec as the share of gear between the 2 specs is common. The only difference in itemization is you want hit on Elemental gear where as you want MP5 on the resto gear.

Just my 2 copper for ya.

I'm trying to level an elemental shaman (19th lvl) with only using drops, quest rewards, what I craft (LW), and no grouping. I did cheat with the heirloom shoulders for the xp bonus.
This toon is still easier for me to level than a geared druid is. I don't see how your in greys at all. I may have a few items 10 levels or so out of date, but nothing that really slows me down. For leveling I just go to a zone that is appropriate for my level and grind quests. If I need a hint on a quest, I just refer to Lightheaded.
This toon is Oldbuzzard on cairne.