They "cool" the processor by issuing HLT commands to CPU during periods of idle. Essentially putting some of the processes in suspend mode when you're not using them. Because of less activity, less electricity is used, thereby less heat. These programs originally were designed to extend battery life on laptops, but then some developers starting applying this principal to desktop PC's running Win9x to take advantage of the cooling benefits, which is really a secondary side effect of the original purpose of conserving power. WinNT and similar kernel OS's have always had this built in, why it was never implemented into Win9x? Who knows.
Anyway, these programs should only be considered strictly as supplementary cooling and not a replacement for a decent HSF. They are only good for keeping the CPU cool during idle or low activity periods. They do nothing for you when your processor is actually performing heavy tasks (ie. gaming). They do, however, aid in quickly bringing the temp down once you're through though.
I personally don't think they're worth it these days, even under Win9x. This is especially true for K7 AMD systems since HLT command functions are already enabled by default in the BIOS (for old Athlon MB's). Newer Athlon motherboards do not allow HLT functions at all regardless of what program or OS you run. This has been disabled because some faster (1.2ghz or higher) systems have a problem with the sharp power spikes cause whenever the system jumps back and forth from activity levels. Doesn't happen to everyone, but there's enough of a problem that AMD has recommended it disabled and MB manufacter's have followed suit. VIA users can of course, by pass this restriction with 3rd party utilities likes Wcredit.