Or, a modern guide to CPU frequency scaling with Linux. Having setup my laptop long ago, I had a strange hybrid of daemons running all trying to scale the frequency of my laptop periodically based on a myriad of different situations. Having decided to fix this, it appears the simplest approach is, as usual, the best.
The way of the future appears to be to let the kernel do all the work with the ondemand govener. The cpufrequtils Debian package will arrange this for you on boot and by default should just work, although you can of course tweak parameters like minimum speed to decrease to and so forth. You can use the cpufreq-set utility to fiddle with settings, or just go into /sys/devices/system/cpu/cpuN/cpufreq/ to tweak them by hand. The many available daemons (cpufreqd, powernowd, etc.) appear to be largely redundant and are probably best removed.
This dropped the temperature of my laptop about 10 degrees C and, apart from a much cooler lap, is so far imperceptible.