Whom to Trust?
The signature could be successfully verified, that means it was really signed with the private key as announced. This key claims it belongs to "John Doe [email protected]".
Yet, your GnuPG setup does not trust in this key. Everybody could create a key for John Doe; all you know is somebody that created a key with user ID John Doe sent you this message.
Verifying Key Ownership
To be sure about whether the sender of this message is really who he claims to be (John Doe), you should get knowledge of his key id (better complete fingerprint) on another, trustfully way (it must not necessarily be secure, as only public information, namely his public key id, is transferred). After that, download and sign his key:
gpg --recv-keys 0x12345678
gpg --sign 0x12345678
All keys you signed (and thus their signatures) will be verified in future.
The Web of Trust
You can also make use of the web of trust. By putting trust on a key, signatures given by that key's owner will also be considered when verifying a key's validity. Have a look at this answer which explains trust, valid keys and the web of trust more in detail: What is the exact meaning of this gpg output regarding trust?What is the exact meaning of this gpg output regarding trust?