When some of my contacts send mails, I see "signed by gmail" in the headers. In my mail client (Mail.app) I can see that it is a Verisign certificate. Is there a way to get a certificate from Google (as the "signed by gmail" mention suggests) or do I have to buy one at Verisign?
Most probably (for GMail with gmail.com sender) you see sign of attached to message DKIM-signature of sending domain (as your text assumes). Something like this
But this is not personal cetificate or user, it's certificate of sending domain, which confirm: this mail really was send by this domain's server. If you'll send you mail over server, which support DKIM, your message will have this badge in recipient's eyes