Hearthpwn

Warrior has a very strong presence even with just the basic starting cards. Haven't gotten a single pack of cards yet? This is the deck for you, completely free where the only requirement is playing the Hero class to unlock the class' basic cards.

Cleave, War Axe, and Heroic Strike provide great early game board control or late game push. Execute to trade off minions in your favor, and as the game goes into the mid-late game the deck starts pulling out some heavy lifters that will trade very favorably for your side while maintaining the momentum from the early game.

Something to note is the Chillwind Yeti, Nightblade, and Kor'kron Elite are all 4 attack creatures. Why is this important? With the Priest class being very popular right now 4 attack is the magic number that the Priest can't touch directly with their Shadow Word: Pain/Death cards, making them very powerful in that alone. Also however, the Nightblade and Kor'kron Elite both hit the board running with their Battlecry and Charge rules respectively.

EDIT: May 22, 2014: First of all I want to give a huge thanks to everyone for all the positive responses. I had forgotten to come back to this since I last updated it near the end of December before multiple crucial Warrior 'balances' and logged in to an awesome surprise with all the comments and +1's.

So to address the deck and some questions: Why Nightblade over Arcanite Reaper? At the time Warsong Commander gave all of your minions Charge and not just >3Attack minions, making the 3xFaceDamage+4Damage Charging very very powerful. Personally I would still keep the Nightblade over the Reaper, because it's another body on the board and the moment it attacks twice it's already better than the 10xDamage from the Reaper.

Loot Hoarder vs Novice Engineer: Constant debate between players about which is better. I prefer the Novice because the battle cry of getting the card immediately is relevant through the entire game, and sometimes you can't afford to wait that turn to attack and kill him against your opponent's minions.

Replacements once you've gotten a few games/packs under your belt: So you're looking to upgrade now that you have a little dust and variety in your cards. Here's a couple different routes:

-2xHerioc Strike, -2xNightblade, -2xBoulderfist Ogre, -2xLord of the Arena. +2xArathi Weaponsmith, +2xDefender of Argus, +2xSunwalker, +1xBattle Rage, +1xSpellbreaker. This leaves your Warsong Commanders in the deck, letting your Weaponsmith and Defender benefit from it. The removal of your 4 bigger late game creatures is turned into a couple Sunwalkers for better Taunt and deck utility with the Spellbreaker to stop that one crucial Legendary/Super buffed minion or Taunt to let you push through with fatal damage. The Defender produces even more Taunt for your opponent to work through as well as a small attack and health buff. Battle Rage should be drawing you anywhere from 2-5 cards, keeping card advantage in your favor as you work into the late game with a full hand. Dust Cost:560.

-2xHerioc Strike, -2xNightblade, -2xBoulderfist Ogre, -2xLord of the Arena, -2xWarsong Commander. +2xSunwalkers, +2xDefender of Argus, +2xBattle Rage, +1xSylvanas Windrunner, +1xCairne Bloodhoof, +1xCommanding Shout, +1xGelbin Mekkatorque. This change up is aiming to bring up the power level, assuming you have been playing for a while/lucky with your packs. Sunwalkers, Defenders, and Battle Rage for the same reasons as above. Commanding Shout for card cycling and allows you to make huge trades with their minions(Remember that the Shout is played on you, meaning that any minions you play after Commanding Shout is played still benefit from it until end of turn). The Legendary: Sylvanas and Cairne are almost auto-included in every competitive deck currently and are the two Legendary cards I highly recommend crafting first. Gelbin is in this because I'm assuming you spent at least $2 in the store and got him for free with your pack, and is a great addition to bring up the power level from completely free to play. Dust Cost:3780 w/Free Gelbin, 5380 if you have to craft Gelbin(Don't, there are much more powerful Legendary cards).

Other great cards to tweak the deck with for cheap: Inner Rage, Rampage, Slam, Cruel Taskmaster, Frothing Berserker, Raging Worgen, Fen Creeper, Loot Hoarder, Harvest Golem, Dark Iron Dwarf, Silver Hand Knight, Stormwind Champion.

I apologize for the wall of text, I  tried to address as many of the questions/concerns as I could. Hope this helps everyone that had any questions or just looking to jump into the game or Warrior Class deck.