You need to have the videos in 3GP or Realmedia(mobile) or MP4. Pc codecs like Divx/Xvid and WMV aren't supported from what im aware unless via 3rd party software.
I've been converting all stuff using Xilisoft iPod Video Converter which converts to MP4 pretty quickly, I've resized to 640 x 480 and they work perfect. Not sure if this is the quickest/easiest way, but works well for me.
__________________
Security is an illusion you buy with your freedom.