Hearthpwn

Overview:
Keep Patchwerk frozen and his weapon destroyed while you mill him.

Mulligan:
Mulligan for cheap freeze and weapon destruction: Freezing Potion, Ice Lance, Frostbolt, Glacial Shard and Acidic Swamp Ooze, Gluttonous Ooze.

Early Game:
Keep him frozen and his weapon destroyed so you don't take too much damage.

Mid Game:
You can begin to play the mill package: Coldlight Oracle (and Youthful Brewmaster on them), Research Project and Jeeves (there will likely be many minions, and he seems to use his hero power on the one with the highest attack). Keep him frozen and use Ice Barrier, Ice Block and Duplicate as needed.

Late Game:
No need for a late game plan, as he won't live that long.

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)