The CSS 3 selector recommendation is pretty clear about both, but I’ll try to show the differences anyway.

Pseudo-classes

Official description

The pseudo-class concept is introduced to permit selection based on information that lies outside of the document tree or that cannot be expressed using the other simple selectors.

A pseudo-class always consists of a “colon” (:) followed by the name of the pseudo-class and optionally by a value between parentheses.

Pseudo-classes are allowed in all sequences of simple selectors contained in a selector. Pseudo-classes are allowed anywhere in sequences of simple selectors, after the leading type selector or universal selector (possibly omitted). Pseudo-class names are case-insensitive. Some pseudo-classes are mutually exclusive, while others can be applied simultaneously to the same element. Pseudo-classes may be dynamic, in the sense that an element may acquire or lose a pseudo-class while a user interacts with the document.

Source

What does this mean?

The important nature of pseudo-classes is stated in the very first sentence: “the pseudo-class concept […] permit selection“. It enables the author of an stylesheet to differ between elements based on information that “lies outside of the document tree”, for example the current status of a link (:active,:visited). Those aren’t saved anywhere in the DOM, and there exists no DOM interface to access these options.

On the other hand, :target could be accessed via DOM manipulation (you could use window.location.hash in order to find the object with JavaScript), but this “cannot be expressed using the other simple selectors”.

So basically a pseudo-class will refine the set of selected elements as any other simple selector in a sequence of simple selectors. Note that all simple selectors in a sequence of simple selectors will be evaluated at the same time. For a complete list of pseudo-class check the CSS3 selector recommendation.

Example

The following example will color all even rows gray (#ccc), all uneven rows which aren’t dividable by 5 white and every other row magenta.

table tr:nth-child(2n) td{
   background-color: #ccc;
}

table tr:nth-child(2n+1) td{
   background-color: #fff;
}

table tr:nth-child(2n+1):nth-child(5n) td{
   background-color: #f0f;
}

Pseudo-elements

Official description

Pseudo-elements create abstractions about the document tree beyond those specified by the document language. For instance, document languages do not offer mechanisms to access the first letter or first line of an element’s content. Pseudo-elements allow authors to refer to this otherwise inaccessible information. Pseudo-elements may also provide authors a way to refer to content that does not exist in the source document (e.g., the ::before and ::after pseudo-elements give access to generated content).

A pseudo-element is made of two colons (::) followed by the name of the pseudo-element.

This :: notation is introduced by the current document in order to establish a discrimination between pseudo-classes and pseudo-elements. For compatibility with existing style sheets, user agents must also accept the previous one-colon notation for pseudo-elements introduced in CSS levels 1 and 2 (namely, :first-line, :first-letter, :before and :after). This compatibility is not allowed for the new pseudo-elements introduced in this specification.

Only one pseudo-element may appear per selector, and if present it must appear after the sequence of simple selectors that represents the subjects of the selector.

Note: A future version of this specification may allow multiple pseudo-elements per selector.

Source

What does this mean?

The most important part here is that “pseudo-elements allow authors to refer to [..] otherwise inaccessible information“ and that they “may also provide authors a way to refer to content that does not exist in the source document (e.g., the ::before and ::after pseudo-elements give access to generated content).“. The biggest difference is that they actually create a new virtual element on which rules and even pseudo-class selectors can be applied to. They don’t filter elements, they basically filter content (::first-line,::first-letter) and wrap it in a virtual container, which the author can style however he want (well, almost).

For example the ::first-line pseudo-element cannot be reconstructed with JavaScript, as it heavily depends on the current used font, the fonts size, the elements width, floating elements (and probably the time of the day). Well, that’s not entirely true: one could still calculate all those values and extract the first line, however doing so is a very cumbersome activity.

I guess the biggest difference is that “only one pseudo-element may appear per selector”. The note says that this could be subject to change, but as of 2012 I don’t believe we see any different behavior in the future (it’s still in CSS4).

Example

The following example will add a language-tag to every quote on a given page using the pseudo-class :lang and the pseudo-element ::after:

q:lang(de)::after{
    content: " (German) ";
}

q:lang(en)::after{
    content: " (English) ";
}

q:lang(fr)::after{
    content: " (French) ";
}

q:not(:lang(fr)):not(:lang(de)):not(:lang(en))::after{
    content: " (Unrecognized language) ";
}

TL;DR

Pseudo-classes act as simple selectors in a sequence of selectors and thereby classify elements on non-presentational characteristics, pseudo-elements create new virtual elements.

References

W3C

• Selectors Level 3
  • 4. Selector syntax
  • 6.6 Pseudo-classes
  • 7. Pseudo-elements
• CSS 2.1 Specification (outdated but still informative)
  • 5.2 Selector syntax:
    

    A simple selector is either a type selector or universal selector followed immediately by zero or more attribute selectors, ID selectors, or pseudo-classes, in any order. The simple selector matches if all of its components match.

  • 5.10 Pseudo-elements and pseudo-classes