In cryptography, you are what you know. If you want to avoid MITM, then Alice must have a notion of who "Bob" is, which means that Bob must know some data element that an attacker does not know. Here, your attacker is the server, which is ideally located to mount an attack.
So the question is: who is Bob ? How is the server "not-Bob" ?
For instance, "Bob" may be defined as: "Bob is a human being who has a driver license with 'Bob' written on it". Or: "Bob is that guy I met in a bar and drank a beer with".
Use of asymmetric cryptography allows you to reduce the problem to a question of trust in a public key. Alice will use what she believes to be Bob's public key. Therefore, Alice only needs some way to make sure that the public key she has is indeed owned by Bob. Ownership of a public key is defined by the control of the corresponding private key: Bob's public key is the key for which the private key is under exclusive control of Bob (e.g. only Bob knows that key, or the private key is in a hardware token -- a smartcard -- that Bob keeps in his wallet).
The basic solution is to have direct exchange of public key. When Alice met Bob in a bar, they gave each other their public keys. Thus, Alice can trust Bob's public key "by definition". For easier exchange (especially after a few beers), Alice and Bob may exchange only "fingerprints", i.e. hash values computed over the public keys. These values are shorter than public keys (e.g. 128 bits, instead of more than a thousand bits for a typical RSA public key) and are sufficient to verify that a given public key matches. In that setup, the server has a repository for public keys, and Alice and Bob only recompute fingerprints to make sure that the server is not playing phony games.
A more advance solution, which alleviates the need for direct alcohol consumption, is to use certificates. A certificate is a box which contains an identity (e.g. a name, such as "Bob") and a public key. The box is signed by a Certification Authority (CA): the CA asserts that the public key really belongs to Bob, by applying its signature. If Alice knows the CA public key, then she can verify the signature on the certificate, and then gain trust in the link between the public key and the identity contained in the certificate.
Certification is delegation of trust. Alice delegates her trust to the CA; supposedly, the CA (let's call it Charlie) went to the bar to meet Bob; through the certificate, Charlie tells Alice: "yeah, that's really Bob's key, he showed it to me after his third pint". Things become a bit murky here, because delegating trust is not easy (especially if Charlie is in the habit of binge-drinking). Delegation can go further, when a CA signs a certificate for another CA. Here, Charlie tells to Alice: "I have not met Bob, but I have met Daphne, who may have met Bob and acted as a CA". Alice, using both the certificate issued by Charlie to Daphne, and the certificate issued by Daphne to Bob, may verify that chain of signatures.
The tricky point here is that while Alice may know Charlie and trust him in his ability to properly identify Bob when he meets him, even under the influence of a gallon of Guinness, Alice does not know Daphne. In the Alice-Charlie-Daphne-Bob chain, Alice must not only trust that Charlie was reliable (he did identify Daphne properly) but also that Charlie was not gullible, i.e. that Charlie would have refused to sign a certificate for Daphne if Daphne was not herself trustworthy. In practical situations, trust rapidly degrades when it is delegated.
When using certificates, there are mostly two possible structures:
Hierarchical CA: there is a single or a few "root CA" which are known by everybody by construction. A CA delegates to another CA (i.e. it signs a certificate with, in the identity, a conventional flag which says: "this public key may be trusted for the purpose of verifying signatures on certificates") only within a contractual agreement which establishes the legal responsibilities of both CA with regards to certification. This means that the delegation is formally defined, and it so happens that it is not easy. A lawyer-compatible certification contract, usually called a "Certification Policy Statement" (CPS), is a 200-pages long document.
Web of Trust: everybody acts as a CA. In the absence of "formal trustworthiness", each individual chain yields only a very small amount of trust. This is meant to be compensated by huge numbers. Alice will accept Bob's key only if she can verify several (many) distinct chains which lead to Bob, going through distinct participants. For instance, Alice will require the Charlie-Daphne-Bob chain but also the Elijah-Fiona-Bob and Gerald-Hillary-Ivan-Bob chains. They're all drunkards, but they may be collectively reliable, in that a fake Bob would have to pay many rounds in order to corrupt one participant of each of the chains that Alice uses (if Alice requires n chains with distinct certificates, then the attacker must corrupt at least n participants).
So the certification business is mostly a matter of procedure: who is a CA, what a CA verifies before issuing (signing) a certificate, how the whole thing stands from a legal point of view, and so on. These procedures are inherently complex and must be supported by details in the certificate format (such as the flag "this public key is a CA key"). The two main standard formats currently defined are X.509 and PGP. X.509 has much support for the hierarchical CA, and is a very tangled mess of standards, formats, practices and committees. PGP (standardized under the name "OpenPGP") has no real support for hierarchical CA; it is meant to be used with a Web of Trust. OpenPGP is simpler than X.509 but more limited, especially if you wish to have a strong legal meaning behind the certificates.
For an IM server, all of this is likely to be overkill. The notion of identity that Alice really wants is probably a notion of repetition: "that Bob is the same Bob than the one I chatted with yesterday". Alice does not know Bob beforehand, but talking with him once establishes his identity in Alice's eye. She just want not to be fooled by another Bob. For that, a simple process such as "Alice's software saves the announced public key of any new chatter, and uses it afterwards" will do the trick. Remember that the key issue is to properly define what notion of identity you are after.
