These headers, included by the mail server, provide a signature of each message. See Gmail Header Format. The public keys are distributed via DNS.
Some other programs can be used by the sender to sign an email message. Programs such as PGP, GnuPG.
Messages sent using PGP, or its free equivalents such as GnuPG, have the signature in the message body itself. Each message can be signed, encrypted, or both. Encrypted messages begin with the header
-----BEGIN PGP MESSAGE-----
followed by some optional headers. The optional headers may include the character set of the decoded message, the program and version that created the message, and an optional comment. The end of the message is noted with
-----END PGP MESSAGE-----
Between these two lines are a series of ASCII characters that represent the encrypted or signed message.
A signed message has the header
-----BEGIN PGP SIGNATURE-----
at the end of the signed message followed by the same optional headers as encrypted messages. The signature is usually three lines of ASCII characters.