Hearthpwn

This is a standard freeze mage modified to deal with Maexxna's hero power. The main strength of this modification is the low-cost battlecry minions. Elven Archer allows you cheap pings and Voodoo Doctor allows you cheap heals as often as you want. The tricky part here is making sure not to play more than 2 minions per turn, as once they aren't being returned to your hand they die.

Crazed Alchemist isn't critical but I put it in to help deal with Spectral Knight and it doubles as a way to easily take out Stoneskin Gargoyle. If you want to replace cards with something like Bloodmage Thalnos or Ironbeak Owl these would be the best candidates to replace.

One funny exception to the freeze/battlecry theme is Wild Pyromancer. I found this card to be EXTREMELY helpful in clearing out Maexxna's 1/1 spiders, as the Pyromancer's card effect occurs after the enemies' deathrattles. This made board clearing extremely easy in the early game, but be sure to only play 1 spell and no other minions with less than 2 health before casting your spell. Even if you're not killing everything off, Maexxna usually has a ton of minions so all those pings for 1 are a huge value.

Secrets should allow you to tank a lot of damage as Maexxna fills up her board. You should clear the deathrattle minions as best as possible so your big AoE spells have maximum effectiveness.

Alexstrasza is mandatory in this deck. Maexxna's hero power lets you use the battlecry multiple times, which is critical. Dropping Maexxna's health to 15 is about the only way you'll be able to deal lethal damage with this deck. If you don't have Pyroblast you can use Fireballs, but if you still can't seem to muster the damage you can try replacing Frost Nova with Ice Lance for example.