DEBIAN repository signing: a step-by-step guide
Solution 1:
Personally, I use the reprepro tool - it does it automatically for me. Yes, this is a tool to manage a whole repository, but it also automatically signs them and asks for my passphrase every time I add a new package.
Solution 2:
The Debian wiki has some automated options: http://wiki.debian.org/HowToSetupADebianRepository
But for the simple case the "howto" appears to be: http://wiki.debian.org/SecureApt#Settingupasecureaptrepository
This bit from the install instructions might help: http://people.debian.org/~osamu/pub/getwiki/html/ch02.en.html#_top_level_release_file_and_authenticity
If you're creating by hand it looks like none of the basic tools have an option to create release files so you might have to deal with apt-ftparchive or similar anyway.