The Lich King will destroy your deck using Purge the Weak, leaving a very trim miracle package that you can use to build enormous Jade Golems quickly.
Mulligan for some of the following: Earthen Scales, Jade Idol, Jade Blossom.
In the first stage, use the first Jade Idol to shuffle and use the Jade Blossoms to ramp up the mana and on turn 6 play one of the Gadgetzan Auctioneers and begin to build up some Golems. If your health begins to run low, use an Earthen Scales, but save one for the big Golems in part three.
Stage two will be over pretty quickly with the 5/5-8/8 Golems making quick work of everything.
In stage three, play the other Gadgetzan Auctioneer if the first died, and continue ramping up, using the last Earthen Scales if needed and smashing the Lich King's face.
My other Frozen Throne / Icecrown decks:
The Lower Citadel
Lord Marrowgar (Control Paladin)
Deathbringer Saurfang (Patron Warrior)
Lady Deathwhisper (Odd Dragon Priest)
The Upper Reaches
Blood-Queen Lana'thel (Zoolock)
Professor Putricide (Elemental Mage)
Sindragosa (Kingsbane Rogue)
The Frozen Throne - The Lich King
Jade Druid vs. The Lich King
Face Hunter vs. The Lich King
Elemental Mage vs. The Lich King
OTK Paladin vs. Lich King
Resurrect Priest vs. The Lich King
Mecha'thun Rogue vs. The Lich King
Murloc Shaman vs. The Lich King
Murloc Warlock vs. The Lich King
C'Thun Warrior vs. The Lich King