Disclaimer: Many inexpensive webcams change internal chipset often. So, while todays bargin webcam may be supported, by the time you buy one its guts may have changed, and you may be SOL.
More and more webcams seem to support the USB Video Class. Both on the cheap end and the high end. This will alleviate the above issue, as if the innards change, as long as it still does UVC, it still works.
These usually advertise the fact by stating 'plug and play' or 'no driver' on the packaging somewhere.
For example the Creative Live! Cam Optia AF has been reported on the UVC-linux mailing list as working well with linux, providing 2MP images.
And this cheap webcam also works at 640*480.