Look into tarsnap, which solves exactly this problem; looking around Colin's site should give you an idea how it works without needing to delve into the code (which _may_ be ok; it's not OSS.)

Basically, generate a tarball, split that into chunks at e.g. zero bytes (tarsnap uses a smarter algorithm), upload any chunks that the server does not have.