What they do is have proofs hosted by the user on different sites (e.g. Github, Twitter) that your client can use to verify that the key is valid. The Keybase server can't fake those without compromising those sites.

In one command, Keybase has acquired maria's public key, her keybase username, and her public identities, and confirmed they're all her, using GnuPG to review a signed tweet and gist she posted. (...) If you trust the client (our reference client is open source), then the server can't give you the wrong key for maria without getting caught or also compromising her twitter and github accounts.