Brief description: force Maexxna to fill his board entirely with 0- and 1-attack minions, heal and armor up each turn, and then use weapons and charges to beat him down in the late-game.
Mulligans: I try to dig for my Voodoo Doctors and Earthen Ring Farseers as much as possible, but keeping cards you'll need later (like Upgrade!) is probably a good idea.
In this match you're goal is to get his board entirely filled with 1-attack creatures (or 0-attack Nerubian eggs) while constantly healing yourself to delay, and later on taking down his health with weapons and chargers. So you'll generally want to kill those two starting spiders so that it spawns 4 small spiders. Leave those alive. From here, just kill anything he plays that has more than one attack with your chargers, so that his entire board is only capable of dealing, at most, 7 damage. He will just use his ability, hit you with the 1-attacks, and pass every turn. No buffs.
Play two total of your Voodoo Doctors and Farseers each turn, and armor up with hero power or Shield Block if possible, so that Maexxna just can not kill you. Keep healing, keep armoring.
Until you get your Arcanite Reaper/Upgrade!, keep chipping away at his health with your Fiery War Axes and Heroic Strike. In the late game, I like to put out one Farseer and one big charge (preferably Leeroy) out each turn, and just go for the face with the charge. Rinse and repeat and you've got yourself a win.