What format are the videos? They'll need to be mpeg4 or H.264 for the iPod. So, if the videos are in another format, you'll need to use a converter

I'm using Windows XP & I use 3GP_Converter (free). Videora's another free one that's popular. If you're using a Mac, someone recently said that iSquint converter was a good one.

There's heaps of info & links in the thread below.
How to transfer music to my iPod (& iTunes)