So from the looks of things, there aren't actually many Easter Eggs in Hearthstone, at least not many discovered yet. It is indeed a little surprising, but to be fair, Hearthstone isn't exactly the largest of games. The closest things to Easter Eggs are actually more like hidden references to the lore of Warcraft.
- If Cairne Bloodhoof is played against a warrior, he says the line "Garrosh, you are not fit to rule the horde" rather than his usual line.
- If Illidan Stormrage is played against a druid, he says the line "Hello, brother" rather than his usual line.
- Millhouse Manastorm, the hero in the tutorial, says a line "Just you wait until I have 10 mana!" This is a reference to the old Millhouse Manastorm card, which had "Battlecry: Put a 'Mega-Blast' card in your hand." Megablast is a 10 mana card that deals 5 damage to all enemies. Reference
- In the Hearthstone credits, there are personalized cards for team members of Hearthstone, many of which seem to reference aspects of the individual person. Reference
- The opening video has an 8 cost Pyroblast; it's now 10.
- If you click on the vegetables long enough you can get a boot.
There are of course individual cards that are references to things in World of Warcraft rather than the actual lore, one of the most obvious being Leeroy Jenkins, but I wouldn't necessarily define these kinds of things as Easter Eggs.
If individual unlisted extras are discovered, feel free to edit this question and tack them on here, so they can be easily organized. However, from what my research could find, these are pretty much the only ones discovered thusfar.