A public-key certificate states that a specific public key belongs to a specific identity. Use this tag for all questions on certificates and authentication of public keys (not public-key authentication, which is authentication _using_ public-keys). If certificates are not a central issue in your question, then don't use this tag.
A certificate is a document that binds a public-key to an identity. This binding is done by the digital signature of the certificate issuer. The idea is that if
- the certificates claims that some key K belongs to some identity I
- the digital signature scheme is secure (i.e. practically unforgeable)
- only the issuer can use the issuer's private key (i.e. the issuer is not compromised)
- an authentic copy of the issuers public key is available
- the issuer is trusted (in a suitable sense)
then a trusting third party must conclude that K indeed belongs to I. If the last assertion is true and the issuer is trusted, then it is commonly called certification authority (CA). A CA is part of what is called a public-key infrastructure (PKI), which typically also include directory services for the distribution of certificates and information about them and revocation status services for checking the validity of certificates.
Unfortunately, in practice life is often a bit more complex than the above idea since there are inconveniences such as certificate chains, lifetimes, and premature certificate revocation that must be dealt with. Yet, the task that certificates help to address remain: how to distribute public-keys in a trustworthy way?
Among the most famous certificates are x509 certificates, which are ubiquitous in networking. ssl/tls, ipsec and S/MIME use X.509 certificates, so whenever you use https on the web, you get your hands dirty. But even some brands of ssh can use X.509 certificates.
Another important certificate type is OpenPGP which is used by former pgp and gpg. These have a much simpler structure than X.509 certificates. The main difference between X.509 and OpenPGP is their underlying trust model. While X.509 is organized hierarchical where there is one and only one certification authority, OpenPGP follows the web of trust where there is no such central instance. (The user is her own certification authority.)
Interested readers may also visit the Information Security SE for questions and answers on security topics.