The simplest thing that worked out of the box was a utility called recordMyDesktop:
Easy to install & use, at least in Gentoo. The way I used it was simple:
recordmydesktop -x X_pos -y Y_pos -width WIDTH -height HEIGHT -o foo.ogv
play it with
Mplayer/Mencoder can also be used to convert it to any other video format if you want, e.g. to AVI:
mencoder -idx input.ogv -ovc lavc -lavcopts vcodec=mjpeg -oac mp3lame -o output.avi
I also need to generate an animated GIF. Here's how:
mplayer input.ogv -vo gif89a:output=output.gif:fps=5 -vf crop=850:562:17:99 -frames 999
If you use the input from the OGV file (not AVI), the quality will likely be better.
You can nonlinearly edit the video by opening the GIF in GIMP and deleting the frames you don't want as layers, then saving it. If you want to alter the speed, make sure you set this during the export and make sure you check the box that tells GIMP to override the default frame delays. You can also use GIMP to crop your video further.
To play your GIF animation, just open it in firefox or any browser.