Miracle Rogue: This is a tough match-up since it revolves around having the right cards to apply pressure and to counter concealed auctioneers. I probably win against 50-60% of the time. I found that the best way to deal with them is to apply lots of early pressure so he uses up his spells on your creatures instead of with his auctioneer. Harvest Golems and Twilight Drakes are really good at that. It’s important to apply lots of pressure because even if you kill all his auctioneers, he can still get all the cards he needs if the game goes on too long.
Fortunately for Paladin, they have lots of ways to kill concealed auctioneers. Equalty + Wild Pyro / Consecration / Avenging Wrath are the most obvious ways. But if you don’t have an Equality in hand, you can also Wild Pyro + Coin + Consecration on turn 5.
Zoo: Probably the hardest match-up, You really want to have Equality + Pyro or Consecration in your opening hand or else you’re going to have a bad time. Aldor Peacekeeper and Truesilver can help slow down the aggression but alone can’t win you the game. Whether you win or not really depends on the starting hands of both players. You have to hope he either plays it slow enough that you can drop bigger creatures or get him to overcommit into an Equality or Consecration.
Handlock: Really good match-up for Paladin. Aldor and Humility help so much against the early Mountain Giants and Twilight Drakes. When you get in Molten Giant range, The Black Knight and Equality combos deal with those easily. Avenging Wrath makes for a really good finisher especially combo’d with Equality
Druid: This has got to be the most one-sided match-up for Paladin. This applies to both token and ramp decks. Save your Aldors/Humility just in case he innervates something big. This is the only match-up where I recommend hanging onto The Black Knight in your opening hand to kill the Druid of the Claw on turn 5. If you’re going second, save your coin for this. Before you play Tirion, wait for both of his Keeper of the Groves to be played. Just play for the long game and make sure your health is over 14 to protect against the Savage Roar combo. With Aldors and Truesilvers, you should be able to get a pretty good card advantage.
Shaman: This can be a hard match-up if the Shaman is able to hold on to board control. They have such good removal that you can really only take control back by playing Equality combos. If you’re able to do that and take control after, you should be good. Try to always kill the Unbound Element before he plays Spirit Wolves. Try to hold on to Tirion until both Hexes are played. It’s actually better to have Ragnaros hexed before Tirion since he gets to deal the 8 damage after he’s dropped.
Control Warrior: Normally a good match-up too. You can often times just outvalue them the same way Paladin can outvalue a Druid. Stampeding Kodo is excellent when you used against Acolyte of Pain and pretty good against Cruel Taskmaster and Armorsmith. Make sure to save your heals until after he plays his Alextrasza. Make sure you have over 12 health unless he has used both Cruel then the number to watch out for is 10.
Keep Harvest golem, Truesilver Champion, Aldor Peacekeeper in all match-ups.
Against control, You want to keep Twilight Drake and Equality if you don’t have a good hand. You can also keep Humility against Warlocks and Druids.
Against Warlocks, you should mulligan like as if it’s Zoo. That means keep Equality, Wild Pyro and Consecration. Fortunately Equality is good against both Handlock and Zoo.
Against face rush decks, Equality isn’t very useful since there isn’t that many creatures and most of them have one health. Twilight Drake is pretty strong because it can kill a lot of minions with it’s high health. Keep Holy Light and Pyro.
Note: I don’t claim to be an expert and a lot of what I said is probably obvious to a bunch of you. I know I’m probably missing a lot of little details, but hopefully this can help out some of the struggling Paladins out there. Feel free to ask lots of questions.