Which authentication protocols build on each other from simple passwords up to certificates, and what weakness does each step fix?

Username/password, then one-time passwords, then challenge-response, then certificate/verify: each step stops sending a reusable secret over the wire.

1. Username/password. The user sends a name and password; the server compares it with a stored (ideally hashed) value. Weak points: the secret travels on every login, so it can be sniffed, phished or grabbed by injected script, and weak passwords fall to dictionary attacks against a stolen hash file.
2. One-time password (OTP). Every password works exactly once (a TAN list in online banking, an RSA SecurID token). A captured password is worthless afterwards, but the user still types and transmits it.
3. Challenge-response. The server sends a random number (the challenge); the client proves it knows the shared secret by encrypting or HMAC-ing it and sending back the response. The secret itself never crosses the network, and a recorded response is useless because the next challenge differs. Used by mobile networks (SIM authentication) and CHAP.
4. Certificate/verify. A public-key variant of challenge-response: the client signs the challenge with its private key, and the server checks the signature with the public key from the client's certificate. The server no longer needs to hold any secret of the client at all. TLS client authentication and IPsec IKE use this as a building block.

Beyond these protocols, any factor can be classed as something you know (password), have (token, smart card, private key) or are (biometrics). Combining two classes gives multi-factor authentication.

Go deeper:

• Wikipedia: Challenge–response authentication — variants, including signatures over a nonce.
• Wikipedia: One-time password — TAN lists, HOTP/TOTP and hardware tokens.
• Wikipedia: Authentication — the knowledge / ownership / inherence factor classes.