If you don't end up simply using rsync as suggested (which I highly recommend. rsync is very good), you should at least read about the rsync diff algorithm. It's fairly simple (I even made a test implementation in Perl, long long ago), and quite effective. They put a lot of thought into solving the problem of efficiently transferring large files over a flaky link. The solution they came up with is really nice. If you're not going to use their program, you might as well use their algorithm. :)

Update: Here's a link to a paper describing the rsync algorithm, for your reference. This is just one copy of many... a quick Google search will show you more.

Update 2: Looking around at the rsync docs, I stumbled upon Andrew Tridgell's PhD Thesis. Chapters 3, 4, and 5 discuss rsync in great detail. Very interesting reading, if I do say so myself. :)