I got this working in linux, and it's fairly easy. I'm still trying to get it working on my win32 machines, and I'll post about that later if I get it working.

This post has most of the details I needed:

http://obfuscatedcode.wordpress.com/2007/04/26/configuring-emacs-for-gmails-smtp/

So I put the following in my .emacs


; install starttls from here (no need for patch)
; http://josefsson.org/emacs-smtp-starttls.html

(setq send-mail-function 'smtpmail-send-it
   message-send-mail-function 'smtpmail-send-it
   smtpmail-starttls-credentials
   '(("smtp.gmail.com" 587 nil nil))
   smtpmail-auth-credentials
   (expand-file-name "~/.authinfo")
   smtpmail-default-smtp-server "smtp.gmail.com"
   smtpmail-smtp-server "smtp.gmail.com"
   smtpmail-smtp-service 587
   smtpmail-debug-info t
   starttls-extra-arguments nil
   smtpmail-warn-about-unknown-extensions t
   starttls-use-gnutls nil)


And followed the instructions to make the .authinfo file containing:

machine smtp.gmail.com login [your name]@gmail.com password [your password]

And finally download, unzip, make and install startttls:

http://josefsson.org/emacs-smtp-starttls.html

You don't need to apply the patch there, it works without as far as I can tell.

Finally you can create and send mail.