Tarsnap lets you say: tarsnap -c -f backup01302009 mysql_dir/
And you can just adjust the date each day. It gives you the luxury of a full dump (anytime you want to restore, just reference backup01302009), but it only actually stores the deltas (making sure not to duplicate data that might be in backup01292009 or backup01282009 and so on). Tarsnap stores the data to S3 so that it's replicated in multiple data centers.
It costs a little more than S3 at 30 cents per GB, but it's metered out so that if you only use 1MB of storage, you'll only be charged 0.03 cents for that storage. You could try creating your own way of doing incrementals, but I doubt you'd get it as efficient as Colin (the math genius behind Tarsnap) and so I doubt you'd get it cheaper. Plus, this way you don't have to deal with it.
And remember, it's hard to fill up a database.* As the Django Book notes: "LJWorld.com's database - including over half a million newspaper articles dating back to 1989 - is under 2GB." So, if they were using Tarsnap, they might be storing 5 or 10GB tops at a whopping $1.50-$3 per month plus whatever the transfer of their deltas was for the month. Oh, and tarsnap compresses the data too. So, maybe they'd be paying $1 or something lower.
* Clearly, if you hit it big time, you might not want to continue paying for tarsnap. However, if you become the next big thing, you can hire someone to deal with it for you.