In the past, converting video was a complicated process for people with a technical know-how of codecs and convoluted jargon that only experts understood. With the evolution of video on the internet, various developers have simplified the process down with some easy to use applications, which the average person can utilize.
The list is long across all the mainstream platforms. However, I live in the Mac world for all my graphics/web and Visual Effects work. The two most common applications I end up using for converting between video formats are FREE.
Video Monkey:
A video encoding application in development which spawned from what was once the tool called Visual Hub. It can convert between many formats and devices, and gives you fine granular control over the settings, should you want to adjust beyond the main presets. (Plenty of Video formats, including all Apple devices, Tivo's, Phones, Games Consoles, and all the mainstream digital formats ie. AVI, MP4, QT, WMV, Flash, Mpeg)
Evom:
This one is more for casual video conversion, but it's FAST. It specializes in Youtube, iTunes, iPod, and AppleTV. As an added feature, it has one-click downloads from Youtube, or any other Flash based file or link you can drag into the conversion window.