Keep Patchwerk frozen and his weapon destroyed while you mill him.
Mulligan for cheap freeze and weapon destruction: Freezing Potion, Ice Lance, Frostbolt, Glacial Shard and Acidic Swamp Ooze, Gluttonous Ooze.
Keep him frozen and his weapon destroyed so you don't take too much damage.
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.
No need for a late game plan, as he won't live that long.
My other Curse of Naxxramas decks:
Anub'Rekhan (Taunt Warrior)
Grand Widow Faerlina (Odd Warrior)
Maexxna (Dragon Priest)
Noth the Plaguebringer (Spell Hunter)
Heigan the Unclean (Control Shaman)
Loatheb (Control Priest)
Instructor Razuvious (Taunt Druid)
Gothik the Harvester (Mill Druid)
The Four Horsemen (Resurrect Priest)
Patchwerk (Freeze Mage)
Grobbulus (Odd Patron Warrior)
Gluth (Divine Shield Paladin)
Thaddius (Control Warlock)
Sapphiron (Fatigue Mage)
Kel'Thuzad (Mill Rogue)