Note: this was done in Ubuntu 9.04 and is more-or-less specific to my repository. You may have different requirements.

1. Generate a GPG key:

$ gpg --gen-key

Select:
kind of key: (1) DSA and Elgamal
keysize: 1024
key expiration: 0

Enter name, email, comment, and passphrase.

Generate entropy (type a lot, use disk)

2. Export key

Look for the line of output that looks like this after generating the key:
pub 1024D/3FD806D7

Use that last section (3FD806D7) for exporting:
$ gpg --export 3FD806D7 > gpg.key

3. Add the GPG key to your clients. One possible solution is to have the key somewhere in the repository and add the key with wget.

e.g. put gpg.key in /var/www/repositoryname and install on the clients using:
$ wget -q -O- http://sub.domain.com/repositoryname/gpg.key | sudo apt-key add -

You can also add the file locally with:
$ sudo apt-key add path/to/gpg.key

You can confirm that the key added by running:
$ sudo apt-key list

4. On the repository server, sign the Release file under dists/jaunty (or whatever suite you're using) and enter your passphrase when prompted:
$ gpg --sign -bao dists/jaunty/Release.gpg dists/jaunty/Release

5. Done! No more authentication issues when running apt* install!

Thanks for this, it has moved me forward.

I'm making a small repository for essential apps on an SDHC card for an Asus eeePC 4G. Everything worked OK except that I get the message:

WARNING: The following packages cannot be authenticated!

Is this some gpg auth issue? I'll trawl around and see what I can come up with but if you can elighten me I'd appreciate it.

Thx.