Say we have Alice and Bob.
Alice sends Bob a message she encrypted with Bob's public key. Bob is the only person who can decrypt it, using his private key. But how can he be certain the message came from Alice?
Suppose he replies, encrypting his message using Alice's public key. Only Alice can decrypt the message. But how can she be certain it was sent by Bob?
Would Alice have to add some kind of public hash to her message so bob can say "This definitely came from Alice?"
Bob has Alice's public key also, and Alice signed the message with her private key. Bob uses Alice's public key to verify the signature.
Go in reverse for Alice to ensure the message was from Bob.
All you have to do now is make sure that Bob has Alice's real public key and not one injected by a man in the middle.
Because you make the assumption that a private key is really "private" --i.e., alice and bob don't leave their usb keys plugged into their machine when they leave work.
The scenario you describe does indeed not provide authenticity. So both Alice and Bob cannot be certain that they are talking to each other. The scenario does only provide confidentiality and as such also not secrecy.
Bob would have to manually confirm with Alice that the public key he thinks is Alice's public key is indeed hers (by calling her and reading it out load and confirming by her voice that it is Alice).
This problem is normally solved with a trusted third party (a Certificate Authority for example, like VeriSign) that issues certificates stating the e.g. Alice is indeed the owner of this particular public key. This is the way it is solved in modern browsers and this is the way all SSL sessions (with your bank of choice) work. A certificate authority signs the certificate from your bank (stating that your bank is indeed the owner of the public key the certificate contains) and your browser has an already built-in certificate from the certificate authority (building a chain of certificates that can be verified).
The scenario you describe is vulnerable to a so called MITM (Man-in-the-middle) attack and not solvable purely with public-key-encryption.