First, a point of terminology: what you describe is symmetric encryption, and a key that's shared between participants is usually known as a secret key; “private key” usually means the part of a key in public-key cryptography that only one participant knows.
There are two ways of disseminating a secret key: it can be transported in some physically secure fashion, or it can be transported using some other form of encryption, commonly public-key cryptography.
There are ways to exchange a secret key that do not require a secret communication channel. The most popular is the Diffie-Hellman key exchange protocol. The principle of Diffie-Hellman is that each participant generates its own key pair, and there is a mathematical operation that constructs a large number from one public key and one private key. This mathematical operation has a very interesting property: the large number can be constructed from Alice's private key and Bob's public key, or from Bob's private key and Alice's public key; you get the same number either way. So Alice and Bob exchange their public keys, and both parties know the large number, which can then be used as a secret key. An eavesdropper can find out both public key, but it is impossible¹ to find the large number from the public keys alone.
The Diffie-Hellman key exchange allows two parties to exchange a secret, no matter who is listening. However, it does not authenticate Alice to Bob or vice versa. Therefore it is amenable to a man-in-the-middle attack: Mallory performs the key exchange with Alice (who believes she's talking to Bob) and separately with Bob (who believe he's talking to Alice), and thus gets to decide or at least know the secret.
When the attacker can intercept and inject messages, more cryptography is needed for the participants to authenticate each other. (A passive attacker effectively means that the underlying transport protocol provides authentication.) The easy way is for each participant to already know each other's public key. If Alice knows Bob's public key:
- Alice can authenticate Bob by sending him a challenge: a random value (a nonce) encrypted with Bob's public key. If Bob can decrypt that value and send it back, Alice knows she is really talking to Bob.
- Bob can authenticate with Alice by sending her a message signed with his public key. Alice verifies the signature to check she is really talking to Bob.
There are many variants that use one of these methods (or yet another variant) in one direction and either the same or a different method in the other direction, or that authenticate in one direction only. For example, SSL/TLS (the cryptography layer for many -s protocols such as HTTPS, SMTPS, IMAPS, etc.) can use several different cipher combinations, and usually authenticates the server to the client but can optionally authenticate the client as well. Diffie-Hellman is slow and cumbersome for this application; the most widely algorithm with public key distribution is RSA.
Of course, Alice and Bob might not know each other's public key beforehand. So they instead rely on a trust chain: Bob sends Alice his public key, alongside a signed statement from a third party that affirms that this key is really Bob's public key. This signed statement is called a certificate and the third partie is a certificate authority. The third party may be known to Bob, or its identity may be confirmed by a fourth party, and so on. Eventually this chain of trust (… vouches for Dominique vouches for Charlie who vouches for Bob) must reach some party Ron that Bob already trusts, meaning that Bob has Ron's public key and trusts Ron to only sign valid certificates.
There are protocols that do not rely on public-key cryptography. In particular, the Kerberos protocol is used in both unix-based and Windows-based networks to establish connections between a client and a server. Kerberos uses a central authentication server called a key distribution center (KDC). The KDC must have the user's password stored in a database, and the client normally prompts the user for the password. To avoid exposing the password, the protocol does not use the password directly, but a cryptographic hash or more generally a key derivation function applied to the password.
With this shared secret, the client and the KDC establish a secure channel and the KDC sends the client a “ticket”. The ticket contains a session key (i.e. a newly generated secret key), as well as a copy of the key that is encrypted with another symmetric key shared between the KDC and the server that the client wants to contact. The client then forwards this encrypted copy to the server. The server decrypts this message to get the session key, and generates a nonce that it encrypts with the session key and sends back to the client. The client then initiates a secure channel with the server, encrypted with the session key, and starts by showing that it could decrypt the nonce: this authenticates the client to the server. A Kerberos session establishment is a variant of the Needham-Schroeder protocol.
¹ In the sense that cryptographers have tried very hard, but the best way they've found to do it requires an unachievable amount of computing power.