This combo heavily relies on this card to add to their card pool. It is also not uncommon that people give it Divine Spirit to double it's health and other, similar cards. What is the best strategy here? The enemy has basically an unlimited card pool and puts out so many cards that it is impossible to do any damage to the hero, because when you put out cards, they get destroyed (overrun) next round.
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:
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.
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).
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.)
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.
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.
Silence the Northshire Cleric using an Ironbeak Owl, the Silence spell, etc.