Hearthpwn

This is a level 10 shaman deck that focuses on minions, totems, and buffs.  I had decent results with this when I started.  Since then, I have added more control spells as I've unlocked them in packs.  Still a good place to start.

Go for your best low cost minions for a starting hand and use your totem spell often.  Try to get as much on the board as possible.  Force them to keep clearing, because if they don't, they will pay dearly.

Attack buff + windfury combo is one of the tricks for this deck.  You have 4 windfury options and 12 buffs that can turn anything on the board into an attacker.  Burst, burst, burst.

The other trick is just overwhelming by constantly spawning totems that the enemy can ignore to their own peril.  Bloodlust FTW!

My favorite thing about the Shaman deck is that I never really feel like I'm out of a game.  Even when I have no attack presence on the board,I can hit a windfury combo or bloodlust a group of low minions and it's gg.  

Once you start getting some spells unlocked for removal, your win rate will greatly improve.  

DISCLAIMER: Before any haters start hating, note that this is just a guide for somebody first starting with a shaman.  It is by no means a high-end ranked deck.

UPDATE 4/16/14: Replaced Ancestral Healing with Novice Engineer.