In conventional password authentication, you prove you are who you claim to be by proving that you know the correct password. The only way to prove you know the password is to tell the server what you think the password is. This means that if the server has been hacked, or spoofed (another machine takes the IP, for example), an attacker can learn your password.
PublicKeyAuthentication works differently. It uses key pairs, of which one key is public and the other must remain private. Anything encrypted with one key can only be decrypted with the other (See PublicKeyEncryption for a fuller description). Others need the public key to send messages to the owner of the private key. After they encrypt their message, only the recipient can reconstruct it. In the same way, only a message encrypted using the private key of a key pair, and therefor by extension the pair's owner, can be decrypted by the public key. Thus, everyone can verify whether the message really originated from him.
PublicKeyAuthentication exploits this to avoid having to send passwords over a network. Instead, your PublicKey is copied to the machines you want access to. When a machine needs to verify your identity, it sends you a block of random data and asks you to sign it, then it checks whether it can be decrypted with your PublicKey. Because only the person with the matching PrivateKey can generate valid encrypted replies, the machine can then be certain of your identity. The machine usually identifies itself the same way. Should the machine be compromised, it is still impossible for an attacker to pretend to be you, because they can grab your public but not your private key, which was never transmitted.
Some well-known applications of PublicKeyAuthentication include PGP or GPG (for signing and encryption email and files), SSH for securely logging in to remote machines, and SSL for secure connections such as for internet banking.
The way PublicKeyAuthentication magic works is clever math. In a lot of situations going one way is easy (like multiplying together two large prime numbers a · b = c) but reversing the operation is much harder (finding the two prime factors of the number we just generated). In another class of algorithms, a parameter c is used to mangle data using a function that appears to be one way and doesn't even allow recostructing the original message with knowledge of c. However, there are correlated parameters a and b (that are kept secret) which make it possible to reconstruct the message using a different function.
The maths involved is still complicated, CPU intensive, and not as secure as conventional cryptography. In practice, therefore, PublicKeyAuthentication is used to transfer the key for a conventional symmetric cryptographic algorithm used to encrypt the actual message sent.