For the S3 side of the comparison, Amazon stores an MD5SUM value for each file, and returns it in the directory listing as the ETag.
For the local side of the comparison, if using code in the github master branch (1.5.0-alpha3+), you can specify a local --cache-file=(some local file) where MD5SUM values are stored the first time the file is synced to S3, so it doesn't have to be read in during future runs to compare. If the file's inode changes (modified date, size), it is recalculated on the next sync. This greatly speeds up the process as all the local files don't need to be read in, just the cache file, while preserving the comparison of using the MD5SUM values. One can also skip using the MD5SUM values with --no-check-md5, if you know already-uploaded files haven't changed.
Older versions of s3cmd don't have the --cache-file option.