Mulligan Strategy For Control Priest

The way to counter this is similar to the way you counter other "fast" decks (fast = lots of card draw and mostly low-cost cards). There are actually several general approaches and one specific approach that applies only to the northshire cleric and not to other fast deck strategies:

1. Get lucky, and draw into something that you can use to eliminate the Northshire Cleric on turn 1 - 3. You can improve your chances a lot by having 2-cost minions that deal 3 damage, or if your class has a low-cost direct damage like the mage's frostbolt, you can eliminate it with pure removal.

2. Use hard removal on the cleric. Hard removal like polymorph, hex and assassinate costs more mana than damage-based removal, but by turn 4 you are likely to have some if you take it, and that should stop their card advantage. Follow up with AoE to clear their board, or get minions that usually trade 2 for 1 (e.g. chillwind yeti, or most things that have more than 5 health; having 4 attack is extra good because priest can't use power words to remove it).

3. By the way, the most mana-effective hard removal for super buff decks (whether northshire or any other minion is the recipient of the buffs) is the warrior's Execute; if you go warrior and you are concerned about this type of deck, you'd be a fool not to take as many Executes as you can get (unless you go arena and simply don't draw them). It's 1 cost, and all you have to do is somehow damage the minion at all -- even if it costs you a minion of your own -- and you can remove the priest's source of card draw. Sure beats the 5-cost Assassinate of the rogue, unless you absolutely do not have any means of damaging the northshire cleric at all, in which case Assassinate is better (it's still poor value to waste an Assassinate on a cleric, though; if you're contemplating that kind of play, you probably already lost.)

4. Specific to the Northshire Cleric: if you simply do not play any minions while you are unable to deal with it, the Northshire Cleric can't draw any cards, because it won't be damaged. The priest may be able to play a neutral card that damages their own minion and then heal it, but that is much less optimal value-wise for the priest than to attack with the northshire cleric into one of your minions that does less than 3 damage. Long story short is, if you don't have any 3-damage minions in your opening hand and the enemy plays a northshire cleric, then don't play any minions until you can remove the cleric in one turn. If you can't eliminate it early game, and the enemy buffs its hitpoints to ridiculous levels, and you don't draw hard removal, you're kinda up a creek; gg. But that's true every time you face a priest, northshire or no, because the buff potential is still there with something like a mogushan warden followed by power word shield and inner light, or an injured blademaster with similar.

5. If you're feeling super confident in your ability to get superior value trades (cards with stats like 2/3, 4/5, 4/6, 6/7, 4/2 with divine shield, etc. are good value trades), you can let the enemy get a full hand; you can even push them over their 10 card limit and make them lose several cards by giving them even more cards, using something like Coldlight Oracle or King Mukla, which both give the enemy 2 cards. You can even attack into the cleric and heal it yourself (if you're a priest, or have a voodoo doctor or something) and you can make your opponent lose quite a few cards this way if they are overdrawn. This can win you the late game due to fatigue or the enemy running out of cards, but to pull it off, you need excellent value cards, good trades, taunt to prevent rushdown, AoE to clear their flooded board, and make every minion count.

6. Silence the Northshire Cleric using an Ironbeak Owl, the Silence spell, etc.

Are there some common rules on which cards to discard immediately?

That's pretty hard to say because it really depends on your build and playstyle. But the cards that cost 5-10 mana should in most cases be removed without thinking. Unless they're some really powerful high quality cards in which case it could be smart to keep one but only if your other cards seem good.

I think it's not worth risking early game by keeping high cost cards unless you're sure you can pull it off.

Besides the mana cost, which factors should I take into account making this decision?

Spell cards:

Some spell cards are more effective late game, even if they cost low amount of mana. Rather remove them unless you feel like they might come in handy early game. Keep good early game spells, especially those that cost low amount of mana and are able to destroy enemy monsters.

Minion cards:

I'd suggest keeping good taunt cards that are up to 5 mana cost. Taunts are very useful and you never know will you get one when you'll really need him later.

Low cost minions that let you draw more cards in any way should be kept as well. Quite useful.

In the end there's no magical formula which will tell you what to keep since you can't know what you're going to get next by drawing. Sometimes you remove cards you don't need early game just to get them replaced with other un-needed cards.