How can one efficiently use S3 to back up files incrementally?

Since this question was last answered, there is a new AWS command line tool, aws.

It can sync, rsync-like, between local storage and s3. Example usage:
aws s3 sync s3://mybucket /some/local/dir/