Go to the Media Object Types page in the site admin area and enable those file types.

I don't have a handy reference for you but in my experience Flash video (FLV) and H.264/MP4 work the best, as both play using Flash. MP4 has the added benefit of working in HTML5 browsers like Safari, so those play on iOS devices.

If you let the GSP encoder (FFmpeg) convert your videos for you, I recommend FLV, which is the default setting. Although the encoder can create MP4 files, for some reason FFmpeg puts the metadata at the end of the file, which prevents the video from playing until it's fully downloaded in the browser. This is a limitation of FFmpeg that I hope they fix.