Unfortunately for some reason Netgear doesn't ship their “GPL” tarball with the cmplzma tool, leaving me with no way to actually change the kernel on my router. Since the whole reason I'm customizing firmware is getting support for IPv6, I definitely did want to replace it. It was somewhat hard to find a working version of this program. There's a .sh version of it somewhere, but at least for me it didn't work.
Eventually, I found an original copy of the program in US Robotics' source tree for the USR9107 router. After looking for some more documentation, it turns out that you should first break out the binary part of the ELF file generated by the Linux build system and compress just that, and figure out the entry point and encode it in the .lz file.
I rewrote everything (including the ELF manipulation part) in a new shellscript: http://wilmer.gaast.net/834root/downloads/cmplzma.sh