Hearthpwn

Legend Proof: http://i.imgur.com/4ezvbUt.jpg

This deck is Taunt Warrior and it is a bit different than other ones that you might see.

I utilize Dirty Rat to cuck quest rogues AND other quest warriors by pulling out cards that can effectively finish their quest. This decklist also runs Acolyte of Pain that has great synergy with Whirlwind and Ravaging Ghoul as cycling for taunts makes finishing the quest that much easier.

A must have for this deck is Deathwing. You might cry when he's sitting in your hand like a brick but he will save your ass in those control matchups that go to fatigue, I promise you.

There's not too much to this deck: fight for board control, use your removal/resources efficiently while trying not to be too wasteful; finish your quest then when the time is right become one with the Rag and start lighting up those insects! 

Mulligans

HARDEST

Paladin - Murloc paladin is a tough matchup because he can drop murlocs down faster than you can crush them and when he starts buffing them it can be over by turn 5. Mulligan for Fiery War Axe and Stonehill Defender. Pray that you get a Brawl by turn 5.

Priest - Dragon priest is one of the tougher decks and if you waste your Executes too early you will be out of resources and if you can't contest with minions you won't have board control. Your priest opponent will likely run potion of madness and cabal priest so you will likely lose your acolyte and alley armorsmith. Count his shadow word pains/deaths and if it gets to fatigue Deathwing can be your savior when the time is right.

MEH

Rogue - similar to pirate warrior but Dirty Rat and removal is key here.

Warrior - It's hard to tell if you're against a pirate warrior until he starts dropping pirates so keep your quest but have a Whirlwind or Ravaging Ghoul and a Fiery War Axe ready. 

EASIEST

Hunter - mulligan your quest and get some removal and it will be a breeze. You just want to kill everything he drops and have removal for his Tundra Rhino, then just survive until your taunt minions do the work for you.

Mage - Burn Mage is surprisingly easy, just stack armor so his burn isn't enough. Dirty Rat is very useful.

Warlock, Druid, Shaman - didn't see a lot of these. For druid, mulligan for Whirlwind, Sleep with the Fishes and Fiery War Axe to deal with his early board presence