I'm assuming you mean deduplication among your own data, in which case, wouldn't compression take care of it? I haven't used tarsnap, what's the benefit over duplicity?
EDIT: Oh, you mean deduplication of files between separate backup sets? That is a nice feature, true.
It is, and tarsnap does it really, REALLY well. I'm backing up what is, on disk, umm... (checks emails) about 15GiB, and I'm currently spending about 8 cents a day. Now if he'd just implement de-dupe across machines on a given account... :)
"This simple offering gives you complete control over organization, compression, deduplication, versioning and meta-data. You are NOT locked into a particular application or protocol, and there are no constraints on file sizes, retention, or access."
Which is great if you can find something that will do deduplication for you and encrypt and handle that the disk isn't actually local. I couldn't.
Also, rsync.net is significantly more expensive than tarsnap in my experience.
EDIT: Oh, you mean deduplication of files between separate backup sets? That is a nice feature, true.