Public-key cryptography. The update server could send a signature along with the update package and the software would check the update contents to make sure the signature matches.
Yes, debian and ubuntu do this using OpenPGP. I'm sure other distros use something similar. Yet another reason to stick with free software.
You saw APT in the supported list right? :-P
That only means that it will work if the user ignores stern warnings telling them the software is untrusted.
Use SSL for the connection to the update server.
A secondary method for authenticating updates would also be wise. When Moxie Marlinspike's null-prefix SSL bug landed, people with vulnerable versions of Firefox were somewhat screwed: Firefox used only SSL to ensure the authenticity and integrity of updates, but SSL was broken, so the update fixing SSL security couldn't be authenticated!
Most of the attack vectors for software updates depend on man in the middle (via DNS spoofing), so this would not help right?