There are a lot of apps that support this. The best I've found is yxplayer in the app store or yxflash from Cydia (same thing for free, but requires jailbreak) -- good compatability, fast with non-HD content, etc. You can move the files over using either iTunes or any program that let's you access the filesystem like iPhoneBrowser, then watch them without the need for any conversions.
Conversion is not a good option:
- Slow (often about 2/3 the length of the video, so you need to plan ahead)
- Lossy (you will lose quality)
- Larger files (usually)
- Generally a pain in the ass
If you must convert, HandBrake (like the accepted answer suggests) is good but doesn't support all formats - xvid4psp in my experience is slightly better.
If you want to convert MKV files with embedded ASS/SSA subtitles (having spent >5 hours looking for a program that will work for this), version 4 of xvid4psp (doesn't work on Win7 x64) is the only program that will do this. v5/v6 of xvid4psp, HandBrake, etc, etc. will not work.