Every host has a public/private keypair that it stores locally. The client stores the last confirmed (or manually added) host key in ~/.ssh/known_hosts. Host key verification is checking the host key against this list.
A lot of people ignore the importance of this part. It is also a bootstrapping issue: At some point you need to get the key into known_hosts. Most people do this by confirming it the first time they connect. That's usually fine for new servers, but what about old servers, e.g. if you're a dev who just joined the company? Most companies don't seem to have a secure way of seeding clients with the initial host keys. I've never seen it.
We solve this with a script that gets them from Puppet (via PuppetDB, its repository of host "facts"). That script has to hard-code the host key of the Puppet host, of course.
Another solution is using the X.509-style certs to sign each host with your own CA, but I haven't looked into that workflow. Edit: It's actually a much nicer workflow. You can sign users, too.