I use patchmaker from clickteam because it's inexpensive, can patch from multiple versions, only stores the differences, and is simple to use.
I use a self-updating mechanism based on the free Subversion system. More on it in this thread. My main goal was to make updating as transparent to the end user as possible. With my current system as long as you have a valid license updating is just a single button click. I also wanted to have a cross platform tool and preferable free (Subversion is both). The added benefits where delta compression meaning faster download times.
@Kai: You don't have any kind of "package" for this system, do you? I'm sure you could get quite a few licenses if you made it simple to use. I was looking at ClickTeam patcher, also. Are there other tools of this type that are cross-platform? What do you Mac coders use for this task?
Well it's just a few hundred lines of C++ code so that's not much of a package .. You should be able to implement it in the proverbial weekend by reading my post.. If you really get stuck I can always help you out.