Shamans are a lot of fun. As others have said they are a little more complex but I personally love their rotations for their damage specs. They have excellent survivability and resto shamans are pretty good healers currently - they are excellent healers in PvP largely due to wind shear, a 2 second spell interrupt with a 6 second cooldown.
Obviously the first choice you should make when leveling is which spec to choose - enhancement (melee), caster DPS (elemental) or healer (restoration).
A good shaman always keeps totems down to give buffs to the group. Over time you will work out that some buffs don't stack with other classes' buffs (for example, strength of earth will not stack with a Death Knight's Horn of Winter).
Then there's rotation management. For elemental, at low levels all you will do is cast lightning bolt for damage. Once you get the lava burst, you will want to cast flame shock to try and keep it on the target at all times. While it's running, you should cast lava burst whenever possible, and otherwise lightning bolt. As you build up charges of lightning shield (which happens as you cast lightning bolts) you can cast earth shock once your lightning shield builds up to around 7. As elemental, make sure you have flametongue weapon at all times. In terms of gear, try and get as much intellect as you can. Try this spec: http://www.wowhead.com/talent#hGGMGRfkzGobhM
As enhancement, you will mainly be using primal strike (until you get storm strike), lava lash and earth shock. You will want to dual wield slow weapons once you get the talent to. Build towards this talent spec: http://www.wowhead.com/talent#hhGMZffG0s0hRGo
As restoration, a good leveling spec to build towards is this: http://www.wowhead.com/talent#hZbhMbZfGbMszRRsd. For healing instances their isn't really a rotation. Things to be aware of is that greater healing wave is basically our best heal and can be cast very fast if you just used riptide due to the tidal waves buff. Healing surge is a quick heal but costs a lot of mana and should be used pretty sparingly. Healing wave is a very cheap heal that doesn't heal a lot but can be good if your party isn't taking much damage. Then there's chain heal which is an excellent one if your whole group is taking damage, and healing rains much later on that puts a circle on the ground that heals whoever stands in it.
I think shaman is one of the more rewarding classes to play and I encourage you to give it a go!