Cheese video recording has still a lot to be improved.
When recording at maximum resolution (1280x1024@9fps here) the video output is really slow, with really low framerate (less than the displayed one), and the audio output is a couple of seconds out of sync.
The issue still stands when recording at lower resolutions at high framerates (like 640x480@30fps).
Sometimes, instead, video is faster than expected and audio still out-of-sync.
Note that I've got two cores at 1,67 GHz both with performance governor set.
I think this happens because the vorbis/theoraenc cannot manage to do the encoding in realtime with so high resolution or framerates.
A possible solution would be to not use resolutions higher than 640x480 when recording video and slow down framerate to 20/2 or 9/1 in the recorded video.
This can be achieved with the videorate element and can be done just in the recorded stream while still displaying the full framerate video source.
Here's an example pipeline that creates a good video with in-sync audio on my laptop:

gst-launch-0.10 oggmux name=mux ! filesink location=test.ogg v4l2src ! video/x-raw-yuv, width=640, height=480, framerate=\(fraction\)30/1 ! ffmpegcolorspace ! tee ! queue ! ffmpegcolorspace ! xvimagesink qos=false sync=false tee0. ! videorate ! video/x-raw-yuv,framerate=9/1 ! theoraenc quality=30 ! queue ! mux. alsasrc  ! queue ! audioconvert ! vorbisenc !  mux.

Another solution would be to record raw data and schedule encoding on idle, but I didn't investigate too much on its feasibility.
Ideas welcome!