Is it possible to find a sender's Public PGP (GPG) key from an encoded message?

Encrypted messages only contain the recipients' key IDs (and even that can be disabled).

You can only find the sender's key ID if the message was also signed – but the signature is encrypted too, so you're out of luck.

Either way, you would only find the key ID, not the key itself.

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 protected]

or alternatively on the keyserver's web interface, like http://pgp.mit.edu/ Sender must have uploaded the key to the keyserver, of course.