Any webcam supporting UVC should work just fine. I find logitech UVC models particularly easy to get going. Only the uvcvideo kernel module needs to be installed (usually is by default). Plug in -> it works!
Best cheapie is the Logitech Quickcam 3000 for business (OEM), got one for about £13. For a nice but pricey cam look at the Quickcam 9000 pro or Quickcam pro for Notebooks (both are essentially the same cam, the latter has a different form factor more suited to notebooks). Typically these nicer models are around £40-£50.
Havin a few issues with skype video calling at the moment (with any cam), all the buttons disappear from the videocall window and I don't see my own thumbnail, also using the hi-res camera hack seems less stable since using it I've had a couple of crashes from Skype. I think these issues may be connected with the version of QT installed; the problems appeared since I rolled back to a more stable QT for other reasons (4.4.0).
Hate to chime in on the Skype for Linux thing but I really hope we see some updates soon. Even some basic improvements and bugfixes to Skype 2 would be welcome.