For future reference, here is the gstreamer pipeline I'm currently using to record videos (with audio) for YouTube:

gst-launch-0.10 \
v4l2src ! 'video/x-raw-yuv,width=800,height=600,framerate=20/1' \
! tee name=t_vid ! queue ! xvimagesink sync=false t_vid. ! queue \
! videorate ! 'video/x-raw-yuv,framerate=20/1' ! queue \
! mux. pulsesrc ! audio/x-raw-int,rate=48000,channels=2,depth=16 ! queue \
! audioconvert ! queue \
! mux. avimux name=mux ! filesink location=test6.avi

For some reason cheese becomes slow for me when I start recording. Probably the theora encoding? I need to investigate further.

I now have tickets for New York! And yay for Bosnia in 2011.