How do revocation certificates work in PGP? I've already read how to build and upload them, but I'm wondering how revocation certificates work, what informations they hold and so on.

Suppose my private key is compromised, but I have a revocation certificate hidden somewhere.
How the keyserver matches the revocation certificate to the compromised key? Is it possible to distinguish my revocation certificate from one generated by an attacker with the stolen private key?
A revocation certificate is a self-signature with signature type 0x20. It only says anybody with access to the private key has revoked it, you cannot distinguish between the real owner and an attacker that got hold of the private key.

You can read the details of what a revocation certificate contains by executing gpg --list-packets [revocation-certificate.asc]. For a revocation certificate of my key prepared in advance if everything including the regular backup fails, this will print:

:signature packet: algo 1, keyid 4E1F799AA4FF2279
    version 4, created 1356517877, md5len 0, sigclass 0x20
    digest algo 2, begin of digest 39 1b
    hashed subpkt 2 len 4 (sig created 2012-12-26)
    hashed subpkt 29 len 1 (revocation reason 0x00 ())
    subpkt 16 len 8 (issuer key ID 4E1F799AA4FF2279)
    data: [8192 bits]


Be aware that also the issue timestamp can be arbitrarily set by an attacker and does not help at distinguishing him from the real owner.