When you make an audio podcast you make a MP3 file. However, this is not a requirement. You can make an audio podcast with aif, ogg vorbis, wav or any other audio file format. The reason people make MP3 is for cross compatibility - all mobile audio players can play MP3.
The same works with video. You can create any kind of video file you like, from highly compressed MPEG1 through MOV MPEG4 to DV all the way to Uncompressed AVI. The reason why people make H.264 M4V files is because they are a particular specification that will play on a particular mobile video player (the iPod).
The secret of podcasting is not in the format, but rather in the RSS file which is pretty much an automatic index file. Downloading media files from a web location is almost as old as the Internet itself. Podcasting is unique because the RSS allows this downloading process to be done automatically in the background.
To create a video podcast that has been created to work on an iPod follow Aanarav's instructions.