The Kindle application framework is Java based. You write "booklets" that work like Java applets. Under the hood the Kindle runs a Linux kernel, so in theory you could just write native C apps, but I doubt Amazon will give developers access to that.
Some more info about hacking your Kindle:

http://igorsk.blogspot.com/2007/12/hacking-kindle-part-3-root-shell-and.html

If everybody stopped laughing and actually RTFA, they aren't claiming 25x compression on anything. The algorithm is targeted at data backup, i.e. very large files and works by comparing incoming data patterns to patterns already stored. Looks like a modification of LZH that uses the compressed file as the pattern table. I'm not saying that it works or that is a breakthrough, but they are not claiming impossible lossless compression on anything. It might actually be interesting for the application it was designed for.