On: Evilgrade is like Firesheep for Software Updates

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.