Apple - QuickTime - Tutorials - Creating Video Podcasts on Mac OS X.
According to the Apple tutorial page, the iPod can play this video format:
MPEG-4 video
File formats: .m4v, .mp4 and .mov
Video: Up to 2.5 Mbps, 480 x 480 pixels, 30 frames per second, Simple Profile
Audio: AAC-LC up to 160 Kbps, 48 KHz, stereo audio
My videos are automatically encoded by my host, vblogcentral.com.
These are the settings vblogcentral.com uses for my video podcasts:
Video: MPEG-4, 500 kbits/sec, 15fps, 320x240
Audio: MPEG-4/AAC-LC, 128 kbits/sec
Saved as .mov
Hope this helps.