Digital Signatures is a type of mathematical techniques used to
authenticate something. They are based on
public key cryptography, where a user has a
public key and a
private key. When a user signs something with his private key, it is possible to use the public key to verify that the actual signature was done by somebody in possession of the private key. In a correct system, finding the private key from the public key as well as signing something without the private key is considered computationally infeasible.
Most digital signature schemes are based on public key encryption, and is done according to the description in Z0z' entry, with the caveat that the hash used has to be a secure hash. However, there do exist schemes that are not based on directly on a cryptosystem - DSA, an algorithm made by the US government to be able to sign but not encrypt, comes to mind.
There exists a special type of digital signature called a blind signature, where the possessor of a private key signs data without knowing what it is, and without later being able to verify that any particular piece of data was signed at a particular time. This plays a significant role in most digital cash schemes.
I disagree with Z0z on digital signatures being of little value without certificates. There are many cases where some form of certificate is useful, but this is not true in anywhere near all cases.
In the PGP world, certificates are done without any central certificate authority, instead relying on a web of trust (where each person effectively act as a certificate authority.)