There's maybe
hundreds of different models out there! One place to start is the linux USB hardware list at
http://www.qbik.ch/usb/devices/
Search for 'webcam' or a brand name. Anything on this list should have an open source driver.
You can save in pretty much any format you like using applications like mencoder.
Some cheap cameras have really bad picture quality, and cannot record smooth motion. A well-known brand with plenty of reports of successful use is a good idea if you want better quality.
Not sure what other interfaces you can get besides USB. I think some cameras do composite-video-out and you can use them with a TV capture card. But then you can use any camera you like.