Hay mil formas. Depende de si puedes o no hacer "trampas", es decir si sólo puedes usar el arduino, o puedes apoyarte, por ejemplo,en un servidor php. En este último caso sería tan sencillo como realizar una llamada al servidor php y que éste se ocupe. Si lo que tienes es que trabajar directamente con un servidor de correo determinado, deberás buscar información sobre el protocolo de correo usado (el más común para correo saliente suele ser SMTP). Supongo que tu caso será este último, así que puedes comenzar con google->arduino+smtp.
Saludos.