[2010-05-11 15:26:01] Processing package widelands 15-1. Uploader: smoku, builder: builder1
[2010-05-11 15:26:03] REJECTED: GPG verification of 'widelands_15-1.dsc' failed. gpg returned 512, output: gpg: Signature made Tue May 11 15:21:46 2010 EEST using RSA key ID 339A95C0
gpg: Can't check signature: public key not found
Check your profile page on Garage; there should be a section there. That said, signing your package is not essential for uploading and I think the Autobuilder signs processed packages at the end.
To answer my own question: GPG key is added to your Garage profile when you got invite to submit apps to extras. Garage doesn't use external (MIT's or any other) GPS server to get the key. If for some reason you need to update the key, the only way is to contact sysadmin at garage [AT] maemo.org.
However, you don't need to sign up your sources anyway. Build your source with