Maexxna uses her 0 mana cost hero power to return two minions to your hand. It is easy to exploit this in order to create conditions that it make nearly impossible for you to lose.
Mulligan: You want cards like Voodoo Doctor, Ice Barrier, and card draw in your opening hand. Don't keep single target nukes, and don't keep extremely high mana cost cards. You'll draw into them as you need them.
Get maximum value out of your battlecry cards. Starting with Voodoo Doctor is great because you can heal yourself for 2 every turn for 1 mana. Be very careful when these cards build up in your hand, however, because you don't want to burn draws. Burning Alexstraza would make you lose. If you have a Coldlight Oracle and a Novice Engineer, ping your own novice to kill it to get rid of the card if your hand is nearly full. Make sure you play enough minions that some stay on the board and you can kill them, always trying to ensure that you don't burn any draws.
Save your Blizzards, Flamestrikes, and Frost Novas until Maexxna plays Sea Giants, Spectral Knights, or other big cards. You can heal almost indefinitely vs 1/2 haunted creepers, so don't waste your board clears on those. If possible, use your Blizzards and Flamestrikes first and save your Frost Novas for later turns, because you can play more spells on the same turn as Frost Nova due to its 3 mana cost.
Eventually, you'll draw into Alexstraza. There are two ways to finish the match. Play Ice Block and freeze the board, then next turn Alex Maexxna down to 15 health, and kill her on the subsequent turn with Fireballs, Frostbolts, or Ice Lances. More reliably, you can clear the board first withBlizzard/Flamestrikebefore you Alexstraza. It takes Maexxna a couple of turns to develop her board, so clearing the board will give you the time you need to finish her off as long as you have >10 health. Also, don't forget that you can Alexstraza yourself indefinitely to stay at 15 health if you need to wait for card draws.
The hardest part of this is not overdrawing, honestly.