This depends greatly on the operating system, so there is no generic answer possible.
In Arch Linux, packages are signed using PGP – not by the original author (who provides only the source code), but by the packager (who compiles the source code into a program and creates the signed package).
The signatures are kept in the package database, along with the rest of package information. (For third-party packages – when you download just the
.pkg.tar.xz file – the signature will be in a second
.pkg.tar.xz.sig file.) The database itself can be signed, but usually isn't.
pacman in Arch Linux verifies signatures against the keys in
/etc/pacman/gnupg.d (managed using
pacman-key); if you don't have the signer's key yet, it will ask to download the key from a keyserver. There are no central "certificate authorities" – PGP uses a Web of Trust algorithm, and the validity of someone's key depends on what other people signed that key. (For example, all official developers' keys are signed by five "master keys", and the master keys are marked as "trusted", therefore all developers' keys are also trusted by the package manager. These keys come by default on all Arch systems, in the
In PGP, since there are no CAs, a key can be revoked only by its owner. To find out about new signatures or revocations, you have to periodically update the cached keys from a keyserver;
gpg --refresh-keys does this for your own keyring, while
pacman-key --refresh-keys updates the keyring used for verifying packages.
In Ubuntu, PGP is also used, but somewhat differently. Packages themselves are almost never signed, they're verified only against the hashsums in the package database, which is signed by an automated process (using a key named "Debian Archive Automatic Signing Key" or "Launchpad PPA for John Smith" or similar).
The signatures are verified against a local keyring too (
/etc/apt/trusted.gpg, maintained using
apt-key) – but differently from Arch, the Ubuntu package manager ignores key signatures and trusts all keys in that keyring, therefore it never downloads keys automatically, and never needs to refresh them. Official keys come preinstalled in various
foo-keyring packages (
debian-keyring and similar), and if one of those keys is revoked, the updated package removes it.
On Windows, programs can be signed using "Authenticode", which is basically X.509 used for code-signing. The signature, as well as the signer's own certificate, is embedded inside the program's
.exe file. (The certificate has to be attached because unlike PGP, X.509 does not have keyservers, despite the original plans X.500 once had.) Differently from Linux, most Windows programs are distributed in compiled form by their authors, so the .exe file is signed by the author directly.
The publisher's certificate is verified against a local database of trusted Certificate Authorities. On Windows, you can see it in
certmgr.msc – the included certificates are decided upon by Microsoft according to requests from CAs. (Note: Supposedly, Windows 7 is able to download the needed CA certificates when needed, so the list in Certificate Manager might be incomplete.)
While verifying the signature, Windows will contact the issuer's OCSP server to check if the certificate hasn't been revoked yet. (The OCSP server address is usually part of the publisher's certificate.) In other words, revocations are handled by the same CA which issued the certificate in the first place. (Note: I'm not sure if OCSP checking is on by default. There is an option to enable/disable it in Control Panel → Internet → Advanced → Security.) In some cases, Microsoft will also mark known-fake certificates as "untrusted" and distribute them the same way as regular updates to the CA list. In
certmgr.msc you can see several certificates having been revoked this way.
Some browsers (such as Opera or Firefox) have their own databases of CA certificates. Those are not used by Windows. Meanwhile, Internet Explorer and Google Chrome use the same Windows database.