Instead of storing the graphics, the graphics editor stores the brush strokes used to create them.
They don't use brushes, just gimp-like filters, like blur, distort, add and others.
Also it uses a modified version o UPX compression.
They don't use UPX, Ryg made kkrunchy (compressor used to make kkrieger) from scratch.
This is from their FAQ. More than two years have passed and I dare to ask: which year?
They aren't going to finish it.
On a side note, I'm thinking about making something like .kkrieger, but it's just a future plan at the moment (although I have texture and map generation code ready, as well as nice player physics).