SSH - the client pubkey has to somehow reach the server's authorized_keys file, and the server fingerprint has to somehow reach the client's known_hosts file.
HTTPS - The root certs have to be present in the client cert store in order for the client to authenticate the servers they connect to.
PGP - People exchange their public keys in key signing parties after verifying each other's identities in person.