Fedora has been using delta updates for some time:

http://fedoraproject.org/wiki/Features/Presto

Normally when you update a package in Fedora, you download an entire replacement package. Most of the time (especially for the larger packages), most of the actual data in the updated package is the same as the original package, but you still end up downloading the full package. Presto allows you to download the difference (called the delta) between the package you have installed and the one you want to update to. This can reduce the download size of updates by 60% - 80%. It is not enabled by default for this release. To make use of this feature you must install the yum-presto plugin: yum install yum-presto.

Basically, the download is smaller, but the package (binary) is then rebuild locally based on the diff files.

So with "delta updates" the download is smaller, but they take some additional time to rebuild the packages / differences locally.

There has been some discussion about using delta updates for Ubuntu, but I am not aware that delta packages are in general use as of yet.

When will Ubuntu include delta updates?

https://wiki.ubuntu.com/UbuntuDebdeltaSupport

https://wiki.ubuntu.com/DebdeltaAptIntegration

Edit: Additional discussion

https://wiki.ubuntu.com/ImageBasedUpgrades

https://blueprints.launchpad.net/ubuntu/+spec/foundations-1305-image-based-updates

https://launchpad.net/ubuntu-system-image

With Ubuntu getting ported to more and more mobile devices, the standard update mechanism through apt and dpkg is starting to show some limitations.

As a result, Ubuntu is now looking at supporting an additional way of updating devices that are based on read-only images. For those devices, we're looking at doing image based updates, basically generating new images on the server side with the usual tools (debootstrap, apt, dpkg), then generate deltas between those images and have the client pull the delta and apply it without ever actually dealing with packages.

We don't intend this to become the only way to update Ubuntu machines, and the use of apt/dpkg will remain supported with most devices having some kind of switch to opt out of image based updates and re-enable apt.