Hearthpwn

Overview:
Create a wall of his stolen and resurrected horsemen to kill him in fatigue or with Mind Blast.

Mulligan:
Mulligan for Power Word: Glory. If you also have a Silence, that's great.

Early Game:
Use turn 1 to get Power Word: Glory on a horseman, if you have your Silence, use it on the horseman first.

From there, just draw cards and use the Acidic Swamp Ooze to deal with Runeblade.

Mid Game:
Use the Kezan Mystic and the Eater of Secrets to deal with the three Paladin secrets he plays (Avenge, Redemption, Repentance).

As the horsemen begin to get buffed, begin using Seance and play your own, rezzing them with Eternal Servitude (to avoid rezzing the Coldlight Oracles), and playing Faceless Manipulator on the horsemen.

When you draw your other Power Word: Glory, you can use it, especially if he buffs with Mark of the Horsemen. Otherwise, heal if needed, you have a lot with Flash Heal and Greater Healing Potion.

You can use the second Silence or yourEntombs on buffed horsemen to remove the threats. 

Late Game:
He will likely be nearing fatigue at this point, and his minions will be close to death or dead, so get rid of his immunity (Mass Dispel) and use Mass Resurrection and Mind Blast, to protect yourself and push to the win.

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)