The iPod's (all the ones doing video), takes video in H.264 video, up to 1.5 Mbps, 640 by 480 pixels (.mov, .mp4 or .m4v).
So if your videos are in any other format, yes you need to convert them. iTunes/Quicktime can do this for you, but sometimes the sound disappears and it's really slow. iSquint is an excellent alternative that does it better and faster.
Note: It's other way's of getting videos besides iTunes Store, and they don't necessarily need to be illegal, but usually needs conversation to be used on an iPod.