They're using a quantizer. Likely http://pngnq.sourceforge.net/ .

To compare yourself:

  wget http://tinypng.org/images/example-orig-c549c73a.png
  wget http://tinypng.org/images/example-shrunk-ec364794.png
  pngnq example-orig-c549c73a.png 
  cmp -b example-orig-c549c73a-nq8.png example-shrunk-ec364794.png

I get one byte of difference between what pngnq produces and their example shrunk version.

BTW, I use pngnq all the time in instances where losing some information is okay. It's a great tool.