[saool]

In the typical case and handwaving a bit:

On registration, the server is handed a site/user-specific key pair _encrypted_ with the master key of the authenticator device (your usb key or your phone, etc), together with the plain-text site/user-specific public key.

On authentication, the server sends down that encrypted blurb, which is temporarily decrypted and then used to sign a challenge the server sent.

So basically the server is used as storage. There are exceptions to this (e.g. resident/discoverable credentials on hardware keys)