There are several ways to do the same thing. Jun Auza blogged about the easiest way possible. For those who want to get their hands dirty, here’s another way to do it:
1. Search videos using Google, YouTube or Minitube
2. Copy the YouTube link
3. Install and use the DownloadHelper add-on for Firefox
4. Convert the downloaded video using the FFmpeg GUI front-end WinFF (sudo apt-get install winff)
Update 1: There’s a nifty program called Mobile Media Converter that does the same trick above.
Update 2: Starting with Minitube 1.2, video download is already built-in (mp4 format)
Update 3: FlashVideoReplacer uses native video playback on YouTube, Blip.tv and Vimeo for now