Asymmetric encryption provides security for messages exchanged between Alice and Bob only insofar as Alice knows Bob's public key and Bob knows Alice's public key. Otherwise, attackers could publish fake public keys and, in effect, pose as Alice when talking to Bob and vice versa.
An historical view of the issue is the following: in older times (say, 50 years ago), Alice and Bob could have talked "securely" only if they knew an initial shared secret. If both Alice and Bob know a shared secret K, then they can use it to encrypt their messages and also to check their integrity (with a MAC). Encryption is against passive attackers (who try to learn the message contents) and MAC is against active attackers (who try to alter the message contents). For a complete secure flow, Alice and Bob would also have to include some sort of numbering in the messages, so that dropped, duplicated or reordered messages are detected.
An initial shared secret is usually hard to establish. Especially when there are more than two Alices and Bobs. If there are n people who must securely talk to each other (securely against external attackers but also against the n-2 other users), then there will be a need for n(n-1)/2 shared secrets, and each user will have to store n-1 secret values (one for each other user to which he may want to talk to).
Asymmetric cryptography makes the problem easier (but not easy). With public/private key pairs, each user stores one private key, and just needs to know the public keys of the other n-1 participants. Public keys are, as the name says, public. They can be shown to the whole world without any ill effect. Presumably, distributing public elements is easier than distributing secrets, because only active attackers are to be feared.
The analogy is that of the Wall. Imagine that there is, in some specific place (say, the central plaza of a town), a big wall made of marble. Everybody can come and look at the wall. On the wall are engraved the public keys of Alice, Bob, Charlie, Dave, Ebenezer,... so that everybody can learn these keys without fear of interference. The whole is guarded and only the official town engraver can add or remove or modify a public key on the wall; and he will engrave, say, Fred's public key only if Fred himself shows him the said key and some valid ID (driver's licence...).
A big wall can be inconvenient, especially for users who do not live in the town where the Wall is located. To allow for remote operation, a nice scheme has been designed: the official engraver is also given a camera, a printer, and a stamp. When the engraver has finished engraving a new public key, he takes a photo of it, prints it a few times, and signs them (with the official stamp). Now, if Alice sends to Bob such a photo, Bob may trust that he has a genuine copy of the part of the Wall which contains Alice's public key: we assume, here, that the engraver's stamp cannot be counterfeited. It is not a problem if some bad guy opens letters and sees that photo: it is public anyway. Making sure that the stamp cannot be counterfeited may prove troublesome, though.
Here comes the really nifty part, which turns this photo business into a complete public-key infrastructure. Instead of a stamp, the official engraver will use a digital signature: the engraver also has a public key, engraved on the Wall too. If Bob knows the engraver's public key, then he can verify any signature computed by the engraver over any photo. That way, by knowing a priori a single public key (the engraver's public key), he can make sure whether any given photo is genuine or not, allowing him to learn the public key of just any other user.
In normal PKI terminology, the photos are the certificates and the engraver is the Certification Authority. Bob must still start somewhere, i.e. know a public key, but only one (the "root") and for an unlimited number of users; it will even work for user's public which do not exist yet. In a full-blown PKI, there may be too many users for a single engraver to manage them all, in which case we can extend the principle with a Master of all Engravers who signs the public keys of subordinate engravers. The Master is then the "root CA" or "trust anchor", and the subordinate engravers are "intermediate CA". To avoid abuse, the photo of the public key for a subordinate engraver is duly marked as "this is the public key of someone who can act as engraver".
Ultimately, once the system with photos works, nobody actually comes to look at the Wall anymore. Only the photos and the signatures are used, and they are sufficient. We may then avoid building the Wall itself (marble is expensive, after all); the "engraver" simply writes down the public key on a piece of paper, duplicates it, and signs the copies directly.
The PKI model explained above is what is done on the Web, with X.509 certificates. Each Web browser (or operating system) knows a priori a few dozens of root public keys, from which the validity of the certificates for the millions of existing HTTPS-powered Web site can be ascertained by verifying the signatures on them. This is a very centralized model; it is called a hierarchical PKI.
Other models exist, in particular the Web of Trust. In the WoT, everybody can act as an "engraver". Since Bob cannot assume that every single user is as trustworthy and reliable as an official engraver, Bob will accept a given public key as being Alice's only if Alice can show many certificates for that key; i.e. Alice could convince Charlie, Dave and Ebenezer that a given key was indeed hers, and Bob happens to know the public keys of these three guys. In that sense, the WoT is more heuristic in nature than a hierarchical PKI. In fact, this is a matter of a definition of identity: in the Wall model, Alice is Alice because she was given an ID card from some "authority" (say, a central state); in the WoT, Alice is Alice because sufficiently many other people know her as "Alice".
The definition of identity is crucial. What does it mean, that Alice and Bob want to "talk securely" ? Bob wants to talk to the "real Bob" which means that she has a preexisting notion of who Bob is, and what makes Bob distinct from, say, Charlie. If Bob is a complete stranger, then it makes no sense to want to talk to Bob exclusively; there is no "Bob" distinct from "Charlie". This notion of identity is what will dictate what kind of PKI you need. If identities come from a centralized structure, then a hierarchical PKI is appropriate. If identities come from mob approval, then a WoT is the right model.
Or maybe you don't want a PKI at all, after all. For instance, Bob may be, from Alice point of view, "the guy who knows the secret password P". Then we are back to the historical setup which predates asymmetric cryptography. We can still do some advanced science, though. Passwords are poor keys because they tend to be guessable through what is known as a dictionary attack. If Alice and Bob just use P as encryption key, then spies may record the message, then try to decrypt them with potential passwords. In order to fix that issue, Password Authenticated Key Exchange algorithm can be used. With a PAKE protocol, Alice and Bob authenticate each other with regards to their common knowledge of P, but a sufficient amount of asymmetric cryptography was injected in the protocol to prevent spies from learning any data which they could use to test a potential password. If Charlie wants to try a potential password P', then he will have to talk to Alice (posing as a fake Bob) or to Bob (posing as a fake Alice), and he will have to do it again for each P' he wants to test. Surely, after a few such failed attempts, Alice and/or Bob will notice that something is amiss. This is how PAKE protocols allow the secure use of low-entropy secrets (i.e. passwords) without needing any kind of PKI.
