The following is a powerful deck for the Mage using fairly basic cards. It uses Spellpower and value minions to help out with spells and to maintain board control. The backbone of the deck are the many spells which can be used to take out enemy minions or reduce their health so that you can trade a worse minion with them.

All deck guides: http://wp.me/P1SfP0-1Fp
HearthStone Beginners Guide: http://wp.me/p1SfP0-1Fd
All Hearthstone Guides: http://wp.me/P1SfP0-1Fb

Mage Deck

Ice Lance (good in combination with freeze)
2x Mana Wyrm (good first turn play with second turn coin follow up)
2x Wargon Infiltrator (good first turn play, trades well with 2 and 3 mana minions)
2x Frostbolt (good removal and control)
Acidic Swamp Ooze (solid 2 drop with potential)
2x Kobold Geomancer (Spellpower, bad 2 drop)
Mad Bomber (good 2 drop or coin play)
2x Frost Nove (Control)
2x Acolyte of Pain (card draw, use hero ability if necessary)
Dalaran Mage (Spellpower and good against 1 health minions)
2x Harvest Golem (good minion, usually trades 2 for 1)
2x Fireball (good removal or finishing move)
2x Polymorph (good removal)
2x Chillwind Yeti (good minion, usually trades 2 for 1)
Gnomish Inventor (card draw and trades well)
Ogre Magi (Spellpower)
Boulderfist Ogre (powerful late game minion)
2x Flamestrike (powerful removal)
Stormwind Champion (powerful end game minion)

Deck Strategy

In the opening hand look for 1, 2 and 3 cost minions that trade well with low cost minions, such as the Worgan Infiltrator or Mana Worm. Avoid using powerful spells for removal since they are often a good suprise to finish off an unsuspecting enemy. Play minions and use the low cost spells to retain board control and use the Spellpower and high cost spells to finish off opponents.