Cryptography is generally used to provide some form of assurance about a message. This assurance can be one or more of four general forms. These forms are message confidentiality, integrity, authentication, and non-repudiation. Up until the advent of public key encryption, cryptography was generally only used to provide confidentiality, that is, communications were encrypted to keep their contents secret. While this encryption generally implies the sender to know the scheme and key in use, and therefore provides some rudimentary authentication, historical symmetric-key encryption schemes do little to provide the assurance of authentication, integrity, and non-repudiation that is available with the use of modern digital signatures.
Digital signatures rely on the ability of public-key encryption algorithms to encrypt a message with a secret key that can then be decrypted via a public key (the opposite of which is done to provide confidentiality--encryption with a public key and decryption only with a secret key). However, to provide digital signing, a signer must use his secret key to encrypt the message--or some representation of the message--that he wants to sign with his private key, so that anyone who knows his public key can use it to verify that only his private key could have signed that message. There are a number of relevant details to proper implementation.
First, the signature itself is useless if the recipients do not have a verified copy of the signer's public key. While perhaps the best method for exchanging that key would be to meet face-to-face, this is often not possible. As a result, many public key infrastructures require the creation of a Certificate Authority whose public key is pre-shared via some trusted method. An example of this would be SSL CA's like VeriSign, whose certificates are pre-installed in most popular browsers by the computer manufacturer. The CA is what's known as a Trusted Third Party, an individual or organization who is trusted by all parties involved in the encrypted communications. It is the duty of this organization to keep its private key safe and secret, and to use that key to sign public keys of individuals it has verified. In other words, in order to save the trouble of meeting face-to-face to exchange keys with every individual you wish to communicate with, you might engage the services of a trusted third party whose public key you already have to go meet these individuals face-to-face. The third party can then sign the public keys and send them along to you, so that you end up with a verified copy without the trouble of exchanging each key pair face-to-face. The details of signing itself we will get to in a moment.
An alternative method commonly used for secure e-mail transmission via PGP or GPG is known as a web of trust. A web of trust is similar to the creation of a certificate authority, with the primary difference being that it is less formal. Rather than creating an organization to act as a trusted third party, individuals will instead sign keys of other individuals they have met in person. In this manner, if Alice has Bob's key, and Bob signs Charlie's key, Alice can trust Charlie's key. Obviously, this can be extended over a very complex web, but this ability is also a great weakness; one compromised individual in the web--the weakest link in the chain of trust--can render the rest useless.
The actual implementation of signing can also vary. One can sign a message simply by encrypting it with his private key--it can be decrypted by his public key, and the act of valid encryption can only be performed by that secret key, thus proving his identity. However, often one may want to sign but not encrypt messages. To provide this functionality at a base level, one might send two copies of the message, one of which would be encrypted. If a reader wishes to verify that the unencrypted message he has read is valid, he can decrypt the duplicate and compare the two. However, even this method is cumbersome; it doubles the size of every message. To avoid this drawback, most implementations use Hash Functions to generate a hash of the message, and use the private key to encrypt that hash. This provides nearly the same security as encrypting a duplicate, but saves space.