GPG Signature Verification is more important step than md5sum checks when installing or updating a software, which can ensure you have real copy from the original distributor. But you must make sure you have correct public key.

I will use Slackware's Public Key to show steps because I am installing it.

First of all, the source of public key must be a trusted source. Like this one from its website, but you better to check if that public key can be used to verify some signed messages, those are believed real messages. A website being hacked isn't a news, you must double check!

You need to import the public key by
wget http://slackware.com/gpg-key
gpg --import gpg-key

You can also create a keyring, for example a keyring for all distro's public keys:
wget http://slackware.com/gpg-key
gpg --no-default-keyring --keyring linux --import gpg-key

You can store all linux distro's keys in that keyring. You will also need to specify the keyring when doing any operations if you choose to use keyring.

Next is to verify:
gpg --verify signed_stuff.asc

When you download something, there might be signed_stuff.sig or signed_stuff.asc aside. You need them to verify signed_stuff.

The results can be
gpg: Signature made Fri 05 Dec 2008 01:05:31 PM CST using DSA key ID 40102233
gpg: Can't check signature: public key not found

means that you need to import the public key first.

gpg: Signature made Fri 05 Dec 2008 01:05:31 PM CST using DSA key ID 40102233
gpg: BAD signature from "Slackware Linux Project "

means that signed_stuff can be forged.

gpg: Signature made Fri 05 Dec 2008 01:05:31 PM CST using DSA key ID 40102233
gpg: Good signature from "Slackware Linux Project "

means that signed_stuff is real.

gpg: Signature made Fri 05 Dec 2008 01:05:31 PM CST using DSA key ID 40102233
gpg: checking the trustdb
gpg: no ultimately trusted keys found
gpg: Good signature from "Slackware Linux Project "
gpg: WARNING: This key is not certified with a trusted signature!
gpg:          There is no indication that the signature belongs to the owner.
Primary key fingerprint: EC56 49DA 401E 22AB FA67  36EF 6A44 63C0 4010 2233

means that signed_stuff is real but the public key isn't trusted.

If you believe that public key is real, then you can
$ gpg --list-keys
/home/livibetter/.gnupg/pubring.gpg
-----------------------------------
pub   1024D/40102233 2003-02-26 [expires: 2012-12-21]
uid                  Slackware Linux Project 
sub   1024g/4E523569 2003-02-26 [expires: 2012-12-21]

$gpg --edit-key 40102233

Then type trust and follow the instructions and type quit to leave. If you verify again, you won't get the warning message.