1. Distribute an RSA public key with your software.
2. Using the associated private key, sign the hash of the latest version of your software, and put that signature online.
3. Each time you update the software, replace said signature with the signature of the hash of the new version.
4. Have the client software periodically fetch that signature file over HTTP, verify the signature, and check that it is up to date.
5. For the love of ${DEITY}, don't install updated versions automatically. If someone steals your RSA signing key, you don't want to hand them a convenient automatic worm distribution system; and in any case, users are generally much happier if they can say "not now please".
Beyond that, approaches vary depending on the complexity of your software. If your software is a complete operating system, you'd probably want something like the FreeBSD Update utility which I wrote; if your software is just a single executable with no data files, you'd probably want something much simpler.
Sending all your client the entire software package again just because your graphic designer moved something two pixels to the left is not advised.
Build the mechanism to handle individual file updates.
Of course -- I was concentrating on security-related aspects, since that's what he seemed interested in.
Build the mechanism to handle individual file updates.
Even better, distribute binary patches instead of downloading complete files -- this can often save 98% of the bandwidth. My "bsdiff" utility (http://www.daemonology.net/bsdiff/) is one of the standard tools for this purpose and is used by FreeBSD, OS X, FireFox, Sophos, and many others.