The Tor Project hosts some bootstrapping servers called directory servers. They contain a list (a directory) with information about all Tor relays currently online. This info about each relay includes the public key. The directory is signed with one of the directory keys. Those keys are distributed along with your copy of the Tor client.
Therefore, the answer to your question is: by having a trusted third party (similar to a certificate authority). Tor relays (called onion routers in the paper) upload their info to the directory periodically. When a client connects to their guard node, they check that the connection is encrypted with the right key, as listed in the directory. Then, when proxying traffic to the middle node (between the guard and exit node), they setup an encrypted connection to that node, proxying through the guard, and checking again that the right key is used (instead of a MITM key) using the directory. Same goes for the final (exit) node.
 "Each onion router maintains a long-term identity key and a short-term onion key. The identity key is used to sign TLS certificates, to sign the OR’s router descriptor (a summary of its keys, address, bandwidth, exit policy, and so on), and (by directory servers) to sign directories."
 "Client software is pre-loaded with a list of the directory servers and their keys, to bootstrap each client’s view of the network."
 "Tor uses a small group of redundant, well-known onion routers to track changes in network topology and node state,including keys and exit policies. Each such directory server acts as an HTTP server, so clients can fetch current network state and router lists, and so other ORs can upload state information."