Hearthpwn

Strategy:

Use lower cost charge minions like Bluegill Warrior and Argent Horserider (and SI:7 Agent's 2 damage) as quickly as possible to break Maexxna's Haunted Creepers into 1/1 Spectral Spiders so she cannot put higher cost minions on the board.

Since she cannot add to the board, you have set up a condition so that if you can stay alive long enough, she will draw through her hand and reach fatigue. 

Don't try to control the board; it is an easy trap to fall into since she keeps putting up minions every turn, but the best strategy is to keep 1-attack minions on her board.

Once you have her 7 Spectral Spiders (or 6 Spectral Spiders and one Haunted Creeper is fine), work on keeping yourself healed until you draw your larger charge minions. Keep hitting her in the face.

Use Alexstrasza to speed up the process. Any charge minion with Abusive Sergeant is helpful. That plus fatigue will kill her. 

Hints: Keep track of how many cards are in your hand as it is easy to quickly get to maximum cards. Play as many as possible or get them on the board so you can continue to draw cards. Try to get your big healers back.  

Cult Apothecary is the MVP of this deck as it gives 14 heal for 7 of her 1-attack minions.