I think 3-4x Shammies can be easier early on if you already have a L70 (or have a nice friend) who can help you run through instances really quick. We call this power-leveling or "boosting" (if you're under 30, I think that's the new term). This is effective until somewhere between L37-40. I got my 3 new shammies to level 40 in about 22 hours or so, if I remember correctly.

With patch 2.3, questing is the way to go... follow a quest guide and go to town doing all the XP-rich quests in the game in a quick, logical order. L40-58 went very, very fast for my guys. Again, a high level main can help fend off gankers (if you're on PvP), assist with super-tough content way over your head, or provide teleport/summon assistance (if you have a mage/warlock main). I was pleasantly suprised by how fast L40-58 went.

Post 58/60, it's more questing in the Outlands, although running instances starts to become more useful for the gear you'll get. Outlands +SpellDmg Mail items are a wonderful thing and you can get a ton of them right at L58 off of various quests. I wouldn't worry one iota about gear pre-L58 for elemental shamans... I was accidentally still wearing Wailing Caverns' leather on one of my guys when he replaced it with a Stormstrike Vest from a Hellfire quest. =P