How to properly setup a verified mail signature?

I've renewed and imported my old self-generated GPG certificate. After setting the new expiration date I've uploaded my cert using gpg --keyserver pgp.mit.edu --send-keys Receiving a test mail, Evolution reports that the mail contains a valid certificate that couldn't be verified. I'm wondering how that should work. Following tutorials on the web, I could create any certificates for arbitrary mail addresses and just publish them on some cert server. So how can I setup a _verified_ certificate accepted by any mail receiver? Is this even possible for accounts on public email providers, e.g. some-account@gmail.com?