Hearthpwn

Unless you know it is control warrior mulligan for the patron matchup.

The Patron Mirror:

• Mulligan for acolyte, death's bite, and patron; depending on your other cards you can also keep inner rage and emperor.
• This MU occurs in two stages.  The first stage lasts as long as it is impossible for frothing OTKs to be played.  This stage lasts until about turn 7.
• Your goal during the first stage is to get a board of 4 patrons on the field: save the coin until you can patron+inner rage+whirlwind on turn 5 if it helps you achieve this goal.  If you have harrison, you can save the coin to prevent your opponent from achieving the same.
• After you get the 4 patrons out, your opponent will either expend a huge number of resources to kill them (which is fine), or more likely he'll be unable to deal with them and you will put him on a lethal clock.
• If you have patrons out, try to keep them at distinct healths so your opponent cannot clear them with multiple whirlwinds on a full board.  Beside keeping your patrons at distinct healths your goal is to survive frothing OTKs before you die, either by killing him with your own frothing OTK or by playing cards like armorsmith and shield block.
• The second stage occurs when one player gets too many patrons out or the mana pool is high enough that frothing OTKs are possible.  If your opponent has too many patrons out to deal with, focus all your energy on obtaining the OTK (and not just barely surviving an extra turn): it is relatively easy to OTK because your opponent has a huge number of minions for you to get whirlwind damage from.
• If neither of you have patrons out by the later turns of the game, then don't be the first player to play them: your opponent may retaliate with an instant OTK.  The game devolves into a standoff where both players try to draw an OTK and to limit their opponent's chance of having one.
• Useful tech cards include Harrison and Brawl.  It is almost never correct to use Harrison on an axe as opposed to a death's bite.

The Control Warrior:

• This is a hard matchup to win.  You have two ways to win, and you must decide which is more viable based on your hand.
• The first is to slam 4-6 patrons on the board early in the game and hope she doesn't have brawl: if she doesn't, you probably win, but in either case proceed with the second plan.
• The second plan is to draw through your deck as fast as possible looking for an OTK.  Since warrior has more than 30 health, it is often the case that you will need 3 whirlwind effects to execute your OTK, though sometimes you can get away with two.  The game is to draw as much as possible while keeping enough inner rages, whirlwind effects, and emperor discounts to ensure the win.
• Try to play it slow and get multiple draws off of acolyte and battle rage if possible.
• A good control warrior may save Harrison to try to mess up your OTK, so account for this!
• The only useful tech card is Harrison.

Unless you know he is handlock, keep the war axe and ghouls.  Always keep death's bite, and depending on the rest of your hand you can keep frothings, acolytes, and armorsmiths as early plays vs zoo.  Very importantly, if he pitches most of his cards hold an execute.

Zoo:
The most useful tech card is a second axe; a second ghoul can also be nice.  This is the protypical aggro matchup in which you try to get a big board of patrons before you die.  Save combo pieces as much as possible without dying if you have patrons in hand, and aim for that big patron swing turn.

Handlock:

• This is a tough matchup which many of the top patron players play in different ways.  You should play out minions early except possibly frothing. 
• When to play turn 3 frothing is a delicate question. Generally, playing a turn 3 frothing gains value if you have a ghoul on the board or a way to kill their first threat, and loses value if you have emperor or warsong in hand.  Almost always you want to play a turn 3 acolyte over a turn 3 frothing.
• You will usually only have one chance to kill a handlock, so constantly calculate OTK potential and sometimes hit face with weapons.  On the other hand, if you can't see a path to drawing OTK don't hurt them at all.
• A moderately useful tech card is brawl.

Unless you know it is a control or freeze mage mulligan for the tempo matchup.

Tempo Mage:

• Mulligan for weapons, ghoul, and slam.  Depending on your hand you can keep frothing, acolyte, and armorsmith as well.
• Your game plan as the patron warrior is to play very aggressively for board control in the early turns, mitigating their board as much as possible.  Slam is great because you can often slam 3/2s and you may need to attack past mirror images.
• As always vs aggro, if you have patrons in hand you should often save activation effects even at the cost of extra damage.  You will win many games by making 4 patrons on turn 5 or 6, even if they have a board presence remaining when you do it.
• Unless you are desperate for the card draw or have nothing else to do, play minions first and shield blocks later.  Once you have board control you will often be living by a knife's edge, but shield block will save you.
• Feel free to let them copy armorsmith--their armor doesn't matter.  You can also let them copy warsong on a warsong patron turn (because your patron will kill the copy for free)
• In late game, it is possible that they could have a single flamestrike, which you should keep in mind as it is their only way to stage a comeback.
• Useful tech cards are ghouls and axes.

Freeze Mage:

• Your game plan as the patron warrior is to fatigue the freeze mage.  You rarely want to play either battle rage in this matchup.
• Keep track of the number of cards they draw.  If you play this right you will be a few cards faster to fatigue, but with enough health that it doesn't matter.
• Don't let yourself get 3-4 cards ahead of them without good reason.  Don't mill yourself, and be willing to send a lonely 2/4 frothing berserker to its death if you have 10 cards in hand.  You can also sacrifice slams without drawing or send acolytes into doomsayers.
• The executes are to be saved for Antonidas and Alex.  Don't burn executes early on doomsayers, and if possible kill emperor by brute force rather than execute.
• Save execute activators as well for when they play the big threats.
• Warsong commander plus a minion can serve as an execute activator or simply as way to kill a threat directly.
• If they are ahead of you in the fatigue race and you are worried you have no answers for antonidas or alex then you can use battle rage to draw.
• Of course, keep your eye out for ways to pop their block with OTKs, but don't do it at the expense of losing too many execute activators.
• A very important part of your game plan is to have huge armorsmith+patron turns, where you whirlwind big boards multiple times to gain dozens of armor.  It can be nice to save both armorsmiths to play together with all of your whirlwind effects, but you won't always get that luxury and it is OK to play them individually as long as you squeeze all the armor you can.
• The useful tech card is shield block.

Grinder and/or Echo Mage:
This is the hardest matchup in the game for Patron.  Try to draw through your deck as quickly as possible.  OTKs are not as effective because of ice block, but if you draw an OTK before they draw an ice block or two OTKs before they draw two iceblocks you can win. Alternatively, try to set up multiple big boards faster than they can draw their flamestrikes.

EDIT: Thanks to banedon and kolento I have a few more points on how to win this now.  Most of the time you want to play frothings early (i.e. on turn 3) for pressure.  This is because frothing OTKs are so easy to iceblock, but the mage may have a tough time removing the early frothing.  It's not a bad play vs either other kind of mage so it's safe to do.  Patron OTKs are much more valuable than frothing OTKs in this MU, because on 10 mana it is difficult for the mage to both flamestrike and defend against a next turn weapon swing.  It is good to flood patrons on turns 5 or 6 before the flamestrike is possible.

• TGT Update: It's now much better to keep axe vs druid in response to the aspirant card.
• Mulligan for frothing, ghoul, death's bite, patrons, and with a favorable hand acolyte.  This MU is fairly even but, depending on how much weapon destruction he runs, slightly unfavorable for you.  Druid is an aggro deck against you, so feel free to play cards like ghoul (or armorsmith, or even just equip axe) on turn 2.  Unless you have acolyte, and sometimes even if you do, play frothing on turn 3.
• As with all aggro matchups, you should often hold cards like inner rages or whirlwind effects to combo with turn 5 or 6 patrons.  Almost always you should take the oppurtunity to make 4+ patrons, even if he has a little board at the end of the play.  Keep an eye on what cards he keeps; if they keep a card that isn't wild growth or innervate you should be more wary than usual of Harrison Jones.
• Druid will occassionally clear your patrons in late game with their combo. At some points in very late game it can be difficult to hold the board against druid, in which case you might want to take risks to set up an OTK rather than continually fighting for board.

Unless you know it is face hunter mulligan for the midrange matchup.

Face Hunter:
If you know you are facing this, you can keep whirlwind in your opening hand. With shield blocks and ghouls or taskmaster this MU is decent.  Play to take board control and use some combination of armorsmith and shield block to climb out of lethal range.  Once you take board control, try to kill him as quickly as possible while being aware that a big board of patrons can yield a large unleash that goes straight to your face. Useful tech cards are ghouls and taskmaster.

Midrange Hunter:
Keep armorsmith, ghoul, weapons, and depending on the rest of your hand you can keep frothing and acolyte. This is another aggro matchup in which it is often correct to go for a board of 4 patrons in the early-midgame. Other than that, just try to go for board control as hard as possible.  It is fine to play a turn 3 frothing, and sometimes fine to play a turn 3 warsong if you have no better play.
If you manage to hold the board they will run out of cards, so don't worry so much about wasting resources unless it gets in the way of a bigger patron combo later.

Useful tech cards are ghouls.  Harrison is (perhaps surprisingly) not particularly impactful vs midrange hunter.

• Mulligan for weapons, slam, and acolyte.
• In this MU your goal at is to survive and draw, repeatedly clearing his board to prevent big oil turns.  It is fairly difficult but sometimes possible to fatigue the rogue.  Therefore, most of the time you will need to switch to an OTK plan as soon as you draw enough combo pieces and/or get an emperor activation.
• The skill in this MU comes from knowing when to switch from defense to offense, as you will often hit her face with weapons for a turn or two or not fully clear her board before the OTK.  Watch out for loatheb and healbot, which are her principal ways to interfere with your OTK.
• Setting up a patron board does very little unless you are sure she doesn't have blade flurry.
  Therefore, patrons should only be used to board clear, to OTK, or to buy time by forcing out a blade flurry response.  In this later use it is often great to combo the patrons you expect to die with an armorsmith, granting enough armor to let you live an extra turn or two.
• Useful tech cards are Harrison and shield blocks.  Save Harrison for big weapons if possible.

At high ranks this is always mech shaman.  Keep slam, weapons, executes, ghouls, and if the rest of your hand is good frothings/acolytes/armorsmiths.  Just try to get the board and then gain a lot of armor: if you ever get board control with enough life you win. Tech cards include Harrison Jones vs Doomhammer, but he shouldn't be kept in your opening hand.

TGT Update: The midrange shaman matchup is still rare, because shaman did not receive too many actually viable tools.  The MU plays similarly to midrange paladin, where patrons are a good delaying and board clearing tactic.  It's quite possible they can clear the first wave of patrons, so preserve enough resources to develop a 2nd wave of patrons or OTK.

• TGT Update: The new dragon priest MU is harder than the pure control priest MU, but in my opinion still winnable.  The game plan and mulligans remain the same.  Try to judge whether the list is more minion heavy or control heavy: if you see cards like shrinkmeister it's less likely they are running 2x lightbomb and chillmaw.  Because they have taunts patrons will often have to be involved in your OTK.
• Mulligan for weapons, execute, slam and acolyte.
• This is the ultimate OTK matchup.  Like vs control warrior, your goal is to draw through your deck as quickly as possible and assemble the combo pieces to do 30 damage.  Patron boards are likely to die to lightbomb or velen's chosen+holy nova, so don't go all in on patrons unless your hand dictates that you must.
• The priest will try to overwhelm you with aggression: that's why it is important to hold execute in the mulligan vs velen's chosen and/or deathlord.  If you survive the early beatdown, the next challenge will be to draw through your deck efficiently in the presence of cabal.
• Do not play a naked 1/3 acolyte or gnomish inventor without expecting it to be cabaled.  Try to play acolytes at the same time as whirlwind effects or to slam your own acolytes.  It's also good to play them before the priest has 6 mana if possible.
• In the late game, always think of your best chance to OTK: let him hit you a few times if it helps you save resources.

TGT Update: Below you can see the original guide, which includes discussion of what to do against the aggro paladin without secrets that runs a lot of charge burst.  Against that kind of deck it's very important to limit divine favor turns, because cards translate directly into damage.  However with the TGT release the most popular paladin is the secret-based deck.  Against secrets, always keep  unstable ghoul and weapons.  Depending on your hand, you can keep armorsmith, frothing, or slam as tempo drops.  If you don't already have a ghoul, keep whirlwind.  If you have any early game, keep patron.  The secret paladins have little way of inflicting damage once the patron player gains board control, so your goal should be to get a board full of patrons as quickly as possible.  Within reason you should focus all your efforts on utilizing your own hand to get patrons out quickly rather than purposely limiting your hand size.  Play around repentance if you can safely do so.

Mulligan for weapons, whirlwind, ghoul, and armorsmith.  Depending on your hand you can also keep slam, and if you suspect midrange you can keep acolyte.

By far the most common paladin is an aggro paladin.  This is a very good matchup for you: just mitigate damage and keep your hand size low when possible to play around divine favor.  Try to get decent value out of every whirlwind effect, as each can represent nearly a full board clear.

Tech cards include Harrison Jones and ghouls.  Ghouls are an amazing turn 2 play vs both kinds of paladin, shutting down muster completely.