Could you find the sender's Public PGP (GPG) key from an encoded message?
Correct, what @grawity said.
Additionally, some email clients do send the senders public key as another attachment automatically.
And/or you can search for the sender's public key on a keyserver using command line:
gpg --search-keys email@example.com
or alternatively on the keyserver's web interface, like http://pgp.mit.edu/ Sender must have uploaded the key to the keyserver, of course.