Details on how to use GPG are not GNUmail specific.
The usual approach is for the recipient to fetch the public key from the keyserver, then verify that the long-form key fingerprint matches the one you have provided in a secure fashion (for example, by meeting in person, checking government issued IDs, and exchanging fingerprints).
Once fingerprints have exchanged, you can make your trust public by signing the public key's identities using your secret key, and either uploading it to the keyservers or (slightly more secure) by emailing a copy of the other person's now-signed public key in an email that has been encrypted using the other person's public key, thus ensuring a person must have both access to the email address and the key which you signed.
Having the recipient trust any GPG key that is attached to the email defeats the purpose of the whole scheme. You, as a sender, surely would not want me to trust signatures from an arbitrary public key sent to me from a fake Svetlana Tkachenko; you'd want me to trust only the one that you gave to me, securely, right?