X.509 is the ISO/ITU standard for public key certificates. The whole point of X.509 was to handle the authentication needs of the X.500 directory scheme, but now it's in fairly common use on "real networks" like the Internet. In addition to certificates, X.509 defines the format and usage of CRLs and various other authentication techniques (mostly fairly simplistic password based schemes).
X.509 is defined using ASN.1, which is very typical of the X.500 system. Unfortunately, the designers decided to include so many strange and obscure things in the certificate format that it's probably nearly impossible to fully support everything that you could (theoretically) include in a certificate. For example, someone created an entirely correctly formed certificate that included an MPEG of his cat.†
Some basic terminology: issuer is the CA (or whoever) who issues the certificate. The subject is the "owner" of the certificate.
The basic certificate is denoted as version 1. This certificate includes various things, including: information about the issuer and subject (name, geographic location, company), the starting and expiration dates of the certificate, the public key of the subject, and a few other things. All of this information is signed by the CA, and the certification information and the signature are bundled together into a structure, ready to be sent off somewhere.
Version 2 certificates were defined a few years after X.509 first came out. People working with PEM found that the v1 certificate format had some problems, especially when lots of people were using them over non-centralized networks like the Internet. So a couple of new (optional) fields where added: unique identifiers for both issuer and subject. The idea was that if a CA had multiple public keys, each one would have a unique field. The value of this field would also be included into each certificate that CA issued, so someone looking at an issued certificate could simply match up the two fields to figure out which key issued the certificate. X.509v2 certificates are not widely used (in fact, I've never seen a single one).
Several years later, the v3 certificate format was defined. This version added a place to put essentially arbitrary extensions to the certificate. Among other things, extensions were defined which replaced the v2 unique id fields, along with ones to hold Internet related information like email addresses, URIs, and DNS names. X.509v3 certificates are widely supported in libraries and applications, though many of the more obscure extensions are simply ignored. The X.509v2 CRL format was also defined at this time (yes, the v2 CRL was defined in the v3 spec, not the v2 spec).
In 2001, X.509v4 was published. This new version didn't change the certificate format at all; as far as I can tell, the main changes were the addition of some very vague language discussing password authentication. The description is so nebulous that it's hard to even see the point to it, though.
The X.509 standards are overly general to the point where it doesn't even define what kind of algorithms you can include in a certificate, or how to format them. So what happens is that people end up creating various profiles of X.509, restricting the options to something that might conceivably be possible to actually support fully. Probably the most common is PKIX, the profile for Internet use, which is defined in RFC 2459. PKIX lets you include RSA, DSA, or Diffie-Hellman keys in a certificate, and defines the formatting for such. There are also profiles for DoD use and various national profiles (the most commonly supported national profiles are the ones from Germany, Sweden, and Finland).
While it's a big bloated freak of a standard, X.509 is what everyone uses. Most IETF standards (TLS, S/MIME, etc), all of PKCS, anything based on X.500 (LDAP, Active Directory), and most everyone else uses exclusively X.509 certificates. OpenPGP certificates provide an interesting and perhaps more usable alternative, but at this time aren't too widely supported in applications (there are some plans for the SSH protocol to support both OpenPGP and X.509 certificates, I hear).
†: See Peter Guttman's X.509 guide at
for information about these, along with some rather funny X.509 commentary.