For quite some time creating proper video-tutorials with Linux wasn't very comfortable.
I tried it with Cinelerra before, but since it's a fully featured video-editor it's too blown up for this simple task. Other solutions, like for example VNC2SWF only record video, but no sound.

A pretty good solution here seems to be recordMyDesktop, it can easily record the screen (or a selected window) and sound.
To make things easier you can choose either to download the frontends GTK-recordMyDesktop or QT-recordMyDesktop. The latter depends on QT 4.2, which as far as I see it won't be standard until distros start shipping KDE 4, which should be around the beginning of 2008.

Not only that this is some nice, easy to use piece of free software, it also uses free codecs for the recordings. Video is compressed with Theora, and Vorbis is used for the sound.

The standard-framerate of 15 FPS is quite suitable for normal recordings, but can be adjusted if necessary.

The first impression I have of this little tool is really good, and I think it might be useful to create some nice videos about GNU/Linux or video-tutorials.