to just encode without doing much editing (except basic cutting and some filters to fix minor problems), Virtualdub is great and it's free. To actually edit properly I am used to using Adobe Premiere, which costs boatloads and you'll basically have to steal it for a small project like this... or go with Apple's Final Cut Pro, which I know nothing about except it might be mac-only for the latest version and it's probably also expensive.
I think you can get the job done with virtualdub alone. I rarely have to use premiere anymore except for nice transitions.
There are 4 major codecs to consider when encoding:
1. divx (avi) - common as dirt and pretty good encoding, everything can play it by now (almost any computer video player can, and a few standalone dvd players can too), not perfect compression but quite good. There's a 3rd party take on this called xvid that has some nice tweaks but it's essentially the same.
2. h264 (avi, mp4) - the best possible compression right now, with x264 being a freeware open source encoder you can use. Apple has started using this. You can get the most bang for your buck with this, the downside is that it's not as well known and widespread as xvid, people who download h264-encoded videos will probably end up having to download the codec. The mp4 format is not playable by every computer video player in the world also tho most major ones now handle it.
3. windows media (wmv, asf): very strong codec, at least as good as divx in terms of compression, but for the most part you must use windows movie maker or some other microsoft software to encode with it. They don't like 3rd party programs being able to open or create wmv's, tho a few exist. Also the ms software often suffers from the overbaking issue, it's usually run with presets and you can't fine tune the compression, and often you'll end up with something that's got a tiny filesize but is also way too blurry (I have a 1 hour 52 min DCC match that got squished to 95 mb, and it's a miracle but you can barely tell the color of the balls). A lot of people think this is a low quality codec because of the tendency of people to use it incorrectly (which is mostly the fault of the crappy software) but it's actually very good. It also can be streamed so that people can watch while they download, which the other formats can't (tho they can sorta fake it).
4. mpeg-2: this doesn't compress the video nearly as much as the other guys, but it's the standard used in all DVDs. So if you wanted to make a DVD later, there wouldn't need to be any special conversion. I don't think that's a good enough reason to use it though, filesizes will be huge.
My advice: Go with divx. Virtualdub plays well with it, it's free to encode and many computer media players decode it without requiring an additional download. It's well established and does the job pretty well. h264 is not well known and most people will almost certainly have to download the codec. WMV is too limited by the encoding software. mpeg2 is too big.
Hope that helped, and let me know if you need instructions on virtualdub or settings or anything else that comes to mind =)