There aren't many desktop recorders for Ubuntu and the one I use is called recordmydesktop. It can be found in Synaptic and the Ubuntu Software Centre.
However, it only outputs to the .ogv format which is no good for uploading to YouTube and I couldn't find a converter. So, after a little Googling I came across a command which will convert it to .avi
To make it a little easier, be sure to record your desktop to your home folder and then when it's done, open a terminal and type:
mencoder thenameofthefile.ogv -ovc xvid -oac mp3lame -xvidencopts pass=1 -o output.avi
And watch it fly! Soon enough, you'll have a file called output.avi which you can rename and upload.
Note: You will need to have mencoder installed