Hearthpwn

Simple, relatively cheap deck to play, but like all decks go, an experienced player will always do better. 

Matchups:

Aggro: As the nature of a midrange deck goes, this deck suffers the most from Aggro. A good mana curve or a bad enemy hand is a 50-50 match up, otherwise you're more likely to lose. 

Midrange: Against Midrange, it's more like a 60-40 or even a 70-30. Due to the efficiency of Murlocs and how they multiply so rapidly (especially due to Finja, the Flying Star) and other cards like Bonemare, you'll most likely crush other Midrange decks. 

Control: Against Control, it's a 80-20. You're the aggro deck here. Play them murlocs and win, and if they get removed by a Dragonfire Potion or something, re-stack your board with minions by using Finja, the Flying Star or The Curator. 

Mulligan: Always Keep and Mulligan for Murloc Tidecaller, Hydrologist, and Murloc Warleader. Almost always keep Grimscale Chum and Rockpool Hunter. 

"Combos": 

These are the combos that are likely to make you gain a huge advantage in the game, or even in some situations, win. Remember them in your mulligans and during the game and it'll help you out hugely. I know some of these are not legit combos, but they give you a huge tempo boost regardless. I'll start out with the more straightforward ones: 

1. Grimscale Chum + any other Murlocs, but it's a huge tempo boost if you are able to buff a Hydrologist or a Rockpool Hunter. 

2. Just like #1, Rockpool Hunter + any other Murlocs, but try to buff cards like Murloc Tidecaller or Murloc Warleader that you need to protect. 

3. Equality+Consecration A classic Paladin board clear. Use it wisely as you won't have many removals after that. 

4. Equality+Primordial Drake A different version of the classic combo, it's a 10 mana combo, but with the positive that you get a 4/8 Taunt. 

5. Finja, the Flying Star+Spikeridged Steed Unless you get hit by a Silence, this can really swing the board to your advantage. 

6. Aldor Peacekeeper+Stampeding Kodo This is basically an Assassinate for Paladins. I can't stress how many times I've gone through huge taunts or huge minions with this. And this combo is fairly easy to pull off, you can easily get Stampeding Kodo through The Curator. 

There are more "combos", but some of them are class specific so I'll mention them later! 

Card Replacements: 

There are budget versions of this deck, but this deck really suffers without some of the key cards. Because there are much more cards that are replaceable then that are not, I'll mention the specific cards that you cannot replace. And of course, I'll only mention the legendary and epic cards that cost a lot of dust to craft. 

1. Finja, the Flying Star Nothing to say here, this card is crucial to swarming your board back with Murlocs. 

2. Tirion Fordring Again, a classic Paladin legendary that sees play in almost every single deck. There's a reason for it. It gets silenced, at least you still have a 6/6 minion. It gets hard removed, you still end up with 15 possible damage in 3 turns. 

3. The Curator Some of you may be surprised, as there are versions of the deck without The Curator. But to this deck, this is necessary. As listed in the combos section, it draws cards that can get you tempo such as Stampeding Kodo and Primordial Drake. And of course, an extra Murloc! Yay! 

4. Murloc Warleader I know this is an epic, so it may cost some dust to craft, but you NEED this for a Murloc deck to work. 

5. Primordial Drake As described in the Combo section, you need this, even when it's not coupled with Equality. 

6. The Black Knight This can be quite controversial, but with the new expansion, there's just a lot of Taunt minions out there. And if you want your murlocs going face, well you better need this card! Can't stress how many The Lich King I killed with The Black Knight. Its battlecry might as well just say "Destroy The Lich King."

Now with possible replacements, but since there are too many, I'll list only some:

-You can certainly drop another card for another Gentle Megasaur. Likewise, you can add or drop Grimscale Chum to your liking. 

-You can certainly drop The Lich King for another huge legendary, or add in another murloc for more early game. 

-You can certainly drop one or two Grimscale Chum or Rockpool Hunter for one or two Vilefin Inquisitor. 

Will update and put class matchups if it gets more upvotes :)