I was looking at this answer and I didn't realize that Minecraft had some Easter eggs in it. Besides the Christmas chest Easter egg, and the sheep Easter egg, what else is there?
Halloween - on October 31st, some mobs will have pumpkins on their heads, and may drop a pumpkin if killed.
Christmas - between 24th - 26th December, chests are reskinned to look like presents
Mobs - naming a sheep or a sheep spawn egg 'jeb_' will result in rainbow sheep (a sheep which cycles through the colours)
Mobs - naming any mob/mob spawn egg 'Dinnerbone' or 'Grumm' will make it render upside-down
April Fools - Mojang often have special jokes for 1st April, e.g Minecraft 2.0 from Apr 2013
Text for the updates/bugfix lists often includes 'Removed Herobrine' as a reference to an urban legend about the game
If you ever kill Notch himself, he drops an apple
Crash logs occassionally include tongue-in-cheek statements such as 'Don't do that again'
On the game's main menu, there is a 0.01% chance that it will say Minceraft instead of Minecraft
If the file with the list of splash text lines (the yellow text on the main menu) is deleted, it will display as 'missingno' which is a reference to the infamous glitch in the early Pokémon games.
Sources - many, many hours of Minecraft (and this wiki page)
In addition to the previous answer...
The text used in the enchantment table is actually from Doom/Commander Keen and is known as the Galactic Alphabet. You actually can transliterate the text to English (there are many more Easter eggs in that alone)*
The texture for zombie pigmen, in the actual texture file, contains a call out to the original artist.
Making your first cake gets you the achievement "The Cake is a Lie" and popular meme in reference to Portal by Valve.
Getting an achievement displays "Achievement Get" which is a reference to Super Mario Sunshine for the Nintendo GameCube.
While fishing you will occasionally pull up leather boots, which is a reference to Zelda game.
*After they changed the enchantment system to include tool-tips, I do not know if the text is still translatable.
As mentioned in the question, if you use a nametag to rename a sheep to
jeb_ (the underscore is required) the sheep will constantly shift hue (also known as "rainbow sheep" or "disco sheep").
The result (and small tutorial) is shown in the following video: