Hearthpwn

This is the deck I used to beat Maexxna normal/heroic modes.

Make sure to upvote if you found this deck helpful and you've used it to successfully defeat her!

Naxx Reminder

Sometimes you will get bad hands/draws as the match progresses, making it harder to set up win conditions and kill her. If this happens concede and try again. It takes a bit of RNG, but eventually you will get good hands/draws. You will beat her, just keep trying! :)

Info

Removed: Razorfen Hunter, Stormwind Knight, Argent Commander, Darkscale Healer.
Added: Blessing of Might, Blessing of Kings, Light's Justice, Hand of Protection in their place.

1. With Blessings you can now push for more damage for 1 turn, specially in the early game.
2. The lower cost of cards allow for easy cycling as well so you can get the heal combo quicker.
3. The overall strategy is the same, only I've cut down the deck's mana curve, and added some useful cards to push for early damage and still maintain the same strategy.
4. This is more fleshed out, and the only dust required is for Earthen Ring Farseer which is not needed, but increases the attempts chance of succeeding substantially.  

Mulligan

You want to Mulligan for Stonetusk Boar, Voodoo Doctor, Bluegill Warrior, Earthen Ring Farseer at the beginning of the game.

Strategy

1. Begin the match by using your charge minions whenever possible to deal damage to her as much as possible. Never target her minions. Keep using your charge minions till you draw a Consecration, or get really low in Health.
2. Sometimes she will put down a Dire Wolf Alpha in this case use a Bluegill Warrior to kill it off instantly, the extra 2 damage can actually kill you.
3. Once she has 4 Haunted Creepers and you have a Consecration in your hand use it. It will flood her board with ones and never be able to use anything else.
4. At that point where she has 7 1/1s on the board you will take 7 damage per turn, this is where your focus will now shift to healing every turn.
5. Use Voodoo Doctors and Earthen Ring Farseers if you have them. The point is to wait till you can cast 2 or 3 healing minions in 1 turn. If it gets to late game begin using Guardian of Kings and Voodoo Doctor each turn for 8 healing per turn.
6. Keep healing constantly using any of the above methods always healing 8+ per turn. Use any remaining mana on cheap charge minions for damage. If you can heal more the 7 damage you would take the following turn use Hammer of Wrath for extra 3 damage and card draw.
7. Make sure you kill off on purpose the boars and bluegills with a Stoneskin Gargoyle if she placed its in order to make room for your healing cards to come back to you on her turn. Keep doing the combo till she dies.
8. In some cases you will have more than enough healing cards in your hand, in this situation flood the board with the cheap Voodoo Doctors and Earthen Ring Farseers to ensure one of them stays on the board next turn, and keep trying to "Flood Heal" until she dies.
9. Remember to use Blessing of Might & Blessing of Kings on your charge minions to push for extra damage, even though its for 1 turn it actually makes a huge difference. But only use said cards when you're ahead in health and can afford to spend the mana on the buffs and still survive on her following turn.
The Hand of Protection is there only due to the low mana cost and flexibility to easily use it in order to cycle cards if the need arises.
Light's Justice is another very low mana cost card, although its only 1 damage, thats 4 damage over 4 turns, which adds up. Especially when you're just healing that turn.
10. Once you reach 10 Mana, the most common strategy from this point is to use Guardian of Kings to heal for 6 Health, and play 1 Wolfrider to push for 3 damage. Effectively only losing 1 health per turn and doing 3 damage. This strategy works as long as you've done sufficient damage before the initial Turn 10 arrives.
In most cases if you happen to get too low you can just skip playing Wolfrider for a few turns, and just use Guardian of Kings & Earthen Ring Farseer to heal for 9 each turn. It will extend the amount of turns you can do with the Guardian of Kings / Wolfrider combo, thus eventually killing her.
11. This is a long match, and it takes a while to kill her, so be ready to spend a bit of time making sure you're following the steps/doing it properly. You might have to concede and repeat due to RNG, but you don't want to spend all day doing it either. You will be her, just take your time and you will succeed! xD