Hearthpwn

Overview:
Create a wall of endlessly reviving taunts using Kel'Thuzad and go face.

Mulligan:
Anub'Rekhan's hero power is pretty intense, so mulligan for you initial removal: Steel Rager, Bloodhoof Brave, Stubborn Gastropod. The only early cards to avoid are Militia Commander and Stonehill Defender, because of his Nerub'ar Weblord.

Early Game:
Turn 1, play Fire Plume's Heart, though you probably won't finish it, it's just extra insurance. The next few turns, should be drawing (Shield Block) and playing your initial protection.

Mid Game:
If he gets too far ahead, play a Brawl, but continuing wearing down his initial control and setting yourself up with cards like Darius Crowley, Ornery Direhorn, Safeguard (magnetize with Zilliax for healing if needed). 

Late Game:
By this point, you should have a strong hold on the board. Once you do, it's safe to play Kel'Thuzad, and the game is yours. In case he dies, you still have Ragnaros the Firelord, The Lich King, and the completed quest.

Video:

My other Curse of Naxxramas decks:
Arachnid Quarter
     Anub'Rekhan (Taunt Warrior)
     Grand Widow Faerlina (Odd Warrior)
     Maexxna (Dragon Priest)

Plague Quarter
     Noth the Plaguebringer (Spell Hunter)
     Heigan the Unclean (Control Shaman)
     Loatheb (Control Priest)

Military Quarter
     Instructor Razuvious (Taunt Druid)
     Gothik the Harvester (Mill Druid)
     The Four Horsemen (Resurrect Priest)

Construct Quarter
     Patchwerk (Freeze Mage)
     Grobbulus (Odd Patron Warrior)
     Gluth (Divine Shield Paladin)
     Thaddius (Control Warlock)

Frostwyrm Lair
     Sapphiron (Fatigue Mage)
     Kel'Thuzad (Mill Rogue)