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 authentica

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)