Illustrator's gradient mesh tool lets you create a grid of points where you can choose a colour for each point. I overlayed the grid onto the sprite and estimated the distance at each point.
He didn't have to color in every single pixel. The gradient mesh lets you create a loose grid of Bezier curves, with a color set at each intersection; Illustrator will interpolate between them.
Yeah I came here to ask how you did the faux-3d cat. It's very subtle, but effective as hell. I thought you were using some kind of fancy parallax shader, but I can see how a displacement map can approximate the same thing. Awesome!
Something I'm really happy with is the psuedo-3d effect on the cat using a displacement map.
I took the cat sprite (http://dn.ht/picklecat/mesmercat.png) and made a "depth map" (http://dn.ht/picklecat/mesmercatdisplacement.jpg) where white is closest and black is furthest. This information is used to determine how far to move the underlying pixels. It's enough to give a subtle illusion of depth.