Although Google definitely frowns upon the practice, there are several high profile methods for downloading videos from YouTube. There are several windows programs for doing this, and a couple command line tools, but I have developed a couple simpler methods that work really well under Linux. These methods are changing as Flash and HTML5 come into prevelance, but as of today, both of these methods work depending on whether you are using the HTML5 version of YouTube or not.
Download YouTube Videos when using Flash Player
You can be sure that you are using the flash player by right clicking on the video. If the bottom menu entry shows "Flash Player", then you are using Flash.
The flash player makes this relatively easy to do. Simply open Nautilus or Dolphin to /tmp. After the video begins streaming to your computer, it will show up at the bottom of the folder list when you sort by Date. It should have a random filename that looks like Flashe6Oshq. At ANY POINT during the streaming, you can move this file, or give it a real name. I always rename it in place and then drag and drop it into my home folder. The only thing you need to do is make sure you don't navigate away or close the tab containing the video streaming until after the video has finished downloading. I typically give these files a .flv file extension, as this is their container format. This has been tested in Firefox and Chromium/Chrome on Linux.
Download YouTube Videos when using the HTML5 Player
This works now with the .h264 file, and it should continue to work with the new .webm videos. HTML5 has built in capabilities for "save file", but YouTube blocks this by placing a transparent element on top of the video. You can hide this video by clicking this bookmarklet: YouTube Unblock. You can drag that link to your bookmarks bar to use it on YouTube. All you need to do after that is to right click on the video and click on "Save Video As". This should work in Firefox and Chromium/Chrome, but I have only tested it in Chromium. These files will be .mp4 encoded (as of today), and in the future .webm encoded.