GnuPG

Create your public and private keys
In case you do not have '.gnupg' direcotry under your Home directory, create it with:

$ mkdir .gnupg

and set up permissions with:

$ chmod 700 .gnupg

Then generate keys with:

$ gpg --gen-key

Choose key type, key length and key expiration.
Then enter your 'User-ID' which consists of 'Name Surname', 'e-mail' and 'comment'.
Then enter your password for using keys.

To publish your public ID:

$ gpg --keyserver pgp.mit.edu --send-keys [e-mail]

Backing up your secret key
This will list keys on your secret keyring:

$ gpg --list-secret-keys

To make backup use:

$ gpg --output [outfile] --armor --export-secret-key [key_identifier as gleaned from above]

This will list keys on your public keyring:

$ gpg --list-keys

To make backup use:

$ gpg --output [outfile] --armor --export [key_identifier as gleaned from above]

key_identifier is usually in the form of something like: ABCDFE01

Depending on your host, you could also just copy the entire .gpg directory if you wanted to do it that way also.

Of course there is the paperkey utility if you need to make a paperkey backup of your secret key:

http://www.jabberwocky.com/software/paperkey/

Evolution integration
At security tab in settings dialog of your email account enter your key identifier.
You can find it by listing keys with:

$ gpg --list-keys

Search for eight characters where now stands 'XXXXXXXX'

pub 1024D/XXXXXXXX 2004-01-01 Name Surname (comment) [email]