The service can verify the user's cert against the identity provider's public key with this information. The service initially contacts the identity provider to get the provider's public key, so the identity provider can infer that someone is attempting to log into the service as one of its users.
Once the service has the provider's public key, it can be cached by the service until it expires, and while it's cached, the service can verify logins without contacting the server again by checking that the cert presented by the user to the service has a legitimate signature from the identity provider's public key.
So if someone logs into HN using their Gmail ID (assuming both services grow support for the protocol), all Gmail knows is that at least one person attempted to log into HN using a gmail address. Who was trying to log in, whether that login was successful, and the number of other people who logged into HN with Gmail after that, are all facts that would be completely hidden from Google.
I'm guessing there's some sort of timestamp there, to prevent someone from just stealing the cert and logging in to whatever they want as that user.
The main actual deployed usage of the technique is in TPM's for direct anonymous attestation. http://en.wikipedia.org/wiki/Direct_Anonymous_Attestation
IBM explains their project here http://www.zurich.ibm.com/idemix/details.html
The original academic work its based on is this http://cs.brown.edu/~anna/papers/cl01a.pdf
A different(and older) technique which, by my understanding, is mainly useful for smart cards, is deployed in a prototype system from microsoft : http://research.microsoft.com/en-us/projects/u-prove/
In short, your browser asks the identity provider to sign a certificate proving that you are [email protected]. The browser will then use that certificate to authenticate you on the site. The site can check this certificate by getting the pubkey from the identity provider. You are never associated with the site you are authenticating against (except on very low traffic identity providers)
Notice that provisioning (steps 1 and 2) and logging into a site (steps 3 and 4) are two completely independent processes, with the browser mediating any identifiable identity-provider-to-target-site communication.