Consider security. Your data will be undoubtedly be stored encrypted but that doesn't amount to a hill of beans if the sign-on system is weak. Some cloud storage providers require you to use your email address as a login name, for example, meaning that anybody who wants to access your data surreptitiously only has to guess your password. If you choose a strong and unique password then this shoudn't be an issue, of course.
As for the actual file uploads, there are essentially two approaches. The first is to back up entire files each and every time. If the file is modified, then the whole thing is backed-up afresh--annoying if you've done little more than tweak a 10GB movie, for example.
The second method is to work out the difference between the old and new files, and only back up the new data--a process known as diffing. This saves bandwidth, and also stops your Internet connection from getting choked with constant backup data.
Bear in mind the load the backup software places on your system. Some services boast of clients that have minimal impact. Some can seriously slow down your computer while they're aggregating files and putting them online. The only way to find out for sure is to use the free trial periods offered by various services.
A major concern is whether the company will stay in business. Startups sometimes offer amazing prices for cloud storage but require a leap of faith on behalf of users that they'll still be around next year. It's possible that even established services could disappear overnight, but more likely the owners will tell you if the service is to terminate, and give you a chance to make other arrangements or retrieve data. Companies like Mozy make a point of explaining how they're backed by a large corporation, making failure arguably less likely.
For those on a budget, it's worth considering a DIY approach using Amazon's Simple Storage Service (S3). Although designed for sophisticated users, S3 is available to anybody who wants it, and at its most basic is surprisingly simple to use. All you need to do is sign up and then create a "bucket," which is S3 terminology for a storage folder. Then you'll have to find some backup software that's able to connect to S3, and provide it with your public and private keys in order to log on.