Before I get into specific card choices, it is important to understand the fundamental flow of how this deck works because it is very unintuitive.
At heart, this is an aggro/tempo deck. It really wants to just kill your opponent on turns 7-9. But wait, Guardian of Kings and Tirion Fordring and TWO Lay on Hands?!?! That's not an aggro/tempo deck right? Unlike other aggro decks, Tides of Battle has a backup plan for when your opponent stops your early aggression. So there is plan A (kill them) and plan B (wait for the tides).
The initial game plan of the deck is to take board control through the use of Nerubian Egg, Shielded Minibot, Scarlet Purifier, and Coghammer. As the game progresses into the midgame, you generally want to clear your opponent's board but you also want to be engineering situations where you can clear their board while still getting a lot of face damage in. For example, Bomb Lobber is a card that often kills your opponent's 4/5 drop allowing you to just keep going for face damage while also strengthening your board.
Coghammer in particular is the heart of this plan. A lot of decks being played right now have a really rough time dealing with a divine shielded minion. Often times if you coin out a Scarlet Purifier, you can follow it up with a Coghammer and confidentially attack face because at 3/4 mana your opponent can't efficiently get through a 4/3 divine shield taunt.
Aldor Peacekeeper is also strong in this role. If your opponent plays a strong 4 cost minion you can often cripple them with aldor and then keep attacking face because your opponent won't be able to make strong trades with their 1 attack minion.
Once you have board control, you can use the paladin buff cards to trade up against your opponent's minions and get even more damage in. The paladin buffing cards have always been really strong but because they require a board presence to be reliable and the paladin early game used to be so weak, they were unplayable. But all that has changed with GvG. Because this deck so aggressively controls the board, the buffing cards are nearly always playable for high value and damage. Just note that you should almost never play a buff on a creature that you just played. Only cast buffs when your are about to attack.
And now to change gears, which is really what this deck is about, what happens when your opponent has the answers to your early aggression? For most aggro decks, they roll over and die because they run out of steam and the control player is able to stabilize. At that point the aggro deck's cards are too weak to compete in the late game.
This is where the idea of tides comes in. Most aggro decks just feebly play their weak minions and watch them die. But with this deck? When the tide of battle is changing against you, you just stop playing cards. You hero power. The late game cards of control decks have to deal with 1/1 recruits incredibly inefficiently and they are forced to deal with them because of how many buffs this deck runs. If your opponent doesn't kill off every single 1/1 token there are decent odds that they just die.
This means that your opponent is typically forced to kill you very slowly. This is where 2 Lay on Hands comes into play. It is critical that during this lull in the battle (typically 12-15 cards deep in the decks) that you've drawn into at least one but preferably both lay on hands. You use double lay on hands to refuel on all your resources. During this refueling period, your opponent honestly can't do much to take advantage of this. Why? Because you're a paladin that plays Equality combo and you just gained 16 life and drew 1/3 of your deck. And during that time period your opponent had to waste their time killing 1/1 dudes so that they don't just die to the huge about of burst damage this deck has through buffs.
Once you've refueled, you Equality combo away whatever tempo advantage your opponent gained during that period and retake the board. Your opponent's cards are more powerful than yours but you are able to play 3-4 cards per turn instead of their 1-2 cards per turn. And so because you are spending more resources in total, your overall plays are going to be stronger. And you use this brief window of power where you can play this many cards per turn to finish them off.
Now, to touch on some specific card choices:
Nerubian Egg is one of the most powerful 2 drops in the game but most decks can't play it because it requires activators that you just can't afford to put in your deck. Zoo can run it because it runs around 10 activators without comprising its overall strategy. This decks runs 8 activators (blessing of might, kings, coghammer, purifier). And like zoo, the egg's uses as an anti-aoe card are very strong as well.
Scarlet Purifier absolutely wrecks a lot of early game openings that rely on deathrattle minions like Hunter. And the high attack low health makes it an extremely juicy coghammer target. Scarlet Purifier also has value against sludge belchers. You'll notice that a lot of this deck's damage comes in at the 2-4 range and the ping from a purifier often helps you get through. These are all secondary benefits though. You should never hold a purifier for the battlecry when you could just be playing it as a 4/3 minion.
Why only 1 Truesilver Champion? Because this deck wants to be making early tempo plays, not value plays. Truesilver in the deck is used as burn more than anything and because the deck already runs so many weapons (muster for battle, coghammer, truesilver, tirion) I found that having a second truesilver was one weapon too many and truesilver is the least useful weapon in this deck.
Bomb Lobber is an extremely powerful tempo minion. He allows you to kill your opponent's minion that they just played without attacking it with your creatures already on board. This allows you to get far more damage in while controlling the board. Lobber is kind of like a neutral soulfire in this role.
Why only 1 Quartermaster? The primary purpose of Quartermaster is to combo with muster for battle in plan B. And because you frequently play your first muster for battle in the early game during plan A, you only have 1 muster for battle left to combo with. This means that the second Quartermaster is nearly always a dead card.
Avenging Wrath is an extremely powerful burn spell that also combos with equality. This card often gives you the reach to finish your opponent off before they can stabilize. For example, if you are playing against a handlock that drops Jaraxxus, you can usually kill them in a single turn with wrath.
Guardian of Kings is in the deck as a way to damage race other aggro decks. For example, if you are playing against hunter you can generally almost match them damage for damage and if around turn 6/7 they ignore your minions and just go face, you can drop guardian of kings and go face yourself and win the race.
TWO Lay on Hands?!?! Yes, two. Double lay on hands is the entire backbone of plan B. Having at least one of your lay hands in the top half of your deck is crucial for plan B to work and this deck can absolutely make use of both during the lull period that I've described above.
Mulligans: You generally want to see any cards that will let you have a strong early game board presence. Nerubian Egg, Scarlet Purifier, Shielded Minibot, Muster for Battle, and Coghammer are the most crucial cards to have in hand.
However, the deck has a more natural curve to it rather than having a ton of early game drops so you should generally keep cards that are ok like Bomb Lobber instead of risking getting Tirion instead. I also almost never keep Truesilver Champion because you have too many other early game weapons and plays that truesilver is almost never a turn 4 play.
There are also some matchup specific cards that are key. Against handlock, Equality is crucial because you can't take them below ~15 health until you have either equality in hand, or Lay on Hands so that you can draw into equality combo. Against hunter, Scarlet Purifier and one of your early weapons (Muster for Battle/Coghammer) are crucial. And against warrior Shielded Minibot can often be a liability against acolyte of pain.
Potential Changes: The one change I suspect will make the deck stronger is trading Tirion Fordring for Dr. Boom. I think Dr Boom fits the deck's overall goals much more strongly and allows for more potential surprise damage via turn 10 Dr Boom + Scarlet Purifier to cause your boom bots to explode immediately for 2-8 damage. Sadly I haven't yet opened him in a pack and so haven't tried him out myself.
Ranking: This is the deck I used to get legend in the first GvG season and I have gotten has high as legend 16.