Hearthpwn

This is a pretty easy Heroic Maexxna deck. While Maexxna isn't that hard, this exploits a specific AI issue that she tends to demonstrate fairly often.

Maexxna has a lot of little spiders in her deck. She even starts with two Haunted Creepers on the board, and has 6 more in her deck. This means that it's very easy to get her to fill up the board with useless trash. Between a rogue's massive amount of board control, and the skeleton of a mill rogue, it's stunningly easy to get her trapped in an AI loop where all she can possibly do is draw, attack with 7 1 attack minions, and pass.

Basically, the core idea of this deck is to get her to play another haunted creeper and maybe a Webspinner, Nerubian Egg, Stoneskin Gargoyle or Haunted Creeper. As long as her board is completely full with less than 8 damage per turn, it's trivial to mill her down to nothing. You will also be fighting with a very full hand.

You ideally want to fill up her board before turn 4. If she plays 2 haunted creepers, your work is very easy. Just go ahead and burst those suckers using things like Backstab or Eviscerate, or even shiv and your weapon. Then it's a matter of making sure you don't accidentally mill off your own Gang Ups or Antique Healbots. Once you hit turn 5 with a Antique Healbot in hand and less than 7 attack on the board, you're pretty much guaranteed a victory. Go ahead and hit her in the face as much as possible, and if you have a healbot and just about any other heal you should be able to eke out a win. Gang up is important to stay at least a little ahead of her in cards. Sinister Strike, Preparation, Shadowstep, Deadly Poison, Eviscerate, Shiv and Perdition's Blade can all be used in the name of face damage to clear up your hand so you won't accidentally mill off your gang ups or other important pieces.

I would advise never playing more than two creatures per round. There's no guarantee that she won't try to trade, and trying to heal through a Sea Giant or Anub'ar Ambusher is extremely difficult to pull off.

For mulligans, I might keep gang up, but you want to aggressively search for cards that will allow you to clear minions you don't want, and pop the haunting creepers as well.  SI:7 Agent, Perdition's Blade, Backstab, Eviscerate, Sap, Deadly Poison and Shiv are all important cards to keep early on. Don't be afraid to prep an Eviscerate or a Shiv if it means filling up that board on that turn.

This card is made from the skeleton of a mill rogue deck. The Coldlight Oracles are generally unnecessary here though, since you don't really need to accelerate the mill. If you ever really want to play rogue, you probably want Preparation anyways, but it can probably be replaced with something like Assassin's Blade, which can be played without fear of getting bounced. Conceal and Cold Blood are also acceptable substitutes, since they can prevent you from milling off Gang Up later.

For an extreme budget version, I would recommend something like this