tl;dr. - Just install the Symbola font (the link on the right half of this page: Unicode Fonts for Ancient Scripts) into your /usr/share/fonts or ~/.fonts folders. For Fedora users, you can
yum install gdouros-symbola-fonts (thanks James in the comments for correcting the spelling. I typed this command for the blog instead of copying/pasting from my terminal. ).
I heard (inaccurately) that Ubuntu should support them (in actuality, the person I heard this from had installed the Symbola font, so he could see Emojicons, but the default Ubuntu user can't). I also heard that it was up to the individual typefaces to include all the Emoji symbols, and if your chosen font doesn't include them, they don't render.
Testing the latter theory, I yanked the Segoe UI font from Windows 8, which is the default font, and I know that Windows 8 fully supports Emoji. This font in Linux though didn't render Emoji icons any better than all my other fonts did.
I heard about Symbola from a Google search, but the blog post I saw that mentioned it was talking specifically about how to use Emoji on your web pages... and it sounded like, "you embed Symbola.ttf using HTML5's new feature, and use that font family for each Emoji icon you want to include on your page... i.e.
<span style="font-family: Symbola">emoji symbol here</span>.
Then a coworker mentioned that the typefaces don't need to include the Emoji icons, as long as font substitution is supported... so I was curious if Linux could do such a thing, so I simply dropped Symbola.ttf in my ~/.fonts folder, and within 2 seconds, all the unrenderable Emoji symbols I saw in my Pidgin chat logs suddenly transformed into the correct symbols like some kind of magic.
So, that's how you do it.
But now I'm curious about what kind of black magic Linux did to suddenly render these symbols. Maybe, when it finds an unrenderable symbol, it scans through the installed fonts until it finds one that provides that symbol...