There's a section about adding video within this sticky
Transferring music to iPod & iTunes

If the videos aren't in the right format (mpeg4 or H.264), you'll need to convert them. I use 3GP converter, some people like Videora & I'm sure there are many others around. Use the forum search to look for video to iPod...you'll find older threads with more info