Generate a new GPG key

gpg --full-generate-key

gpg (GnuPG) 2.0.22; Copyright (C) 2013 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Choose key-pair type, default is a good choice

Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
Your selection? 1

Choose key size, be paranoid and use max. available

RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048) 4096
Requested keysize is 4096 bits

Choose validity of the key, 1 year is a good choice

Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 1y

# Double check expiration according to your validity choice
Key expires at Tue 04 Jul 2017 07:57:46 PM CEST
Is this correct? (y/N) y

Enter user data

GnuPG needs to construct a user ID to identify your key.

Real name: John Doe
Email address: john@example.com
Comment: This indeed is my key!

Confirm your data

You selected this USER-ID:
    "John Doe (This indeed is my key!) <john@example.com>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? O

Enter passphrase and hit <OK>

 Enter passphrase

 Passphrase ***************_________________________

      <OK>                             <Cancel>

Re-enter passphrase and hit <OK>

 Please re-enter this passphrase

 Passphrase ***************_________________________

       <OK>                             <Cancel>

Key is going to be generated... (takes a while)

We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy. 

Ends up in something like this

gpg: key AA6CFB50 marked as ultimately trusted
public and secret key created and signed.

gpg: checking the trustdb
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   5  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 5u
gpg: next trustdb check due at 2017-07-04
pub   4096R/AA6CFB50 2016-07-04 [expires: 2017-07-04]
      Key fingerprint = 6279 69BF 8644 4D64 CA63  1F55 962C 1715 AA6C FB50
uid       [ultimate] John Doe (This indeed is my key!) <john@example.com>
sub   4096R/109F9230 2016-07-04 [expires: 2017-07-04]

Congratulations, you now own a GPG key.

Make sure you upload your public key to a key-server so it can be used for verifications.