Starting with the hardest step, find a reasonable photo. Crop it to be square, preferably some multiple of 48 pixels.
Next the photo needs to be converted to a 48x48 Portable Network Graphics file of 725 bytes or less. You can use your favorite graphics editor or give this a try:
djpeg face.jpg | ppmnorm | pnmscale -width 48 -height 48 | ppmquant 15 | pnmtopng > face.png
Fiddle with the number of colours on ppmquant until the resulting face.png is 725 bytes or less. Best to avoid space-consuming options like transparency and comments, with such little space using more colours is better. Here's a typical result:
A nice page describing the Face header and its specification is at quimby.gnus.org/circus/face.
Evolution's Face plug-in is already activated on Fedora 8 and Ubuntu 7.10. It requires the PNG file to be one line of Base64-encoded text at ~/.evolution/faces.
openssl base64 -e -A < face.png > ~/.evolution/faces
The resulting ~/.evolution/faces needs to be 998 bytes or less.
Restart Evolution. The face must be added manually for each and every composed e-mail, by selecting Insert | Face prior to pressing Send.
Thunderbird has the MessageFaces add-on. Download the add-on. Install it with Tools | Add-ons | Install. Configure it with Tools | Add-ons | MessageFaces | Preferences then select the account and Set Face. This brings up a file selector, so select the face.png file. This add-on automatically adds faces to outgoing mail and automagically takes care of the Base64 encoding of the PNG file.
Interesting usability differences for similar implementations of the same function.
As a side note, the overkill of using OpenSSL for Base64 encoding springs from the gradual retirement of command-line Base64 utilities from typical installations: uuencode (currently in the Fedora package sharutils), mimencode (the retired metamail) and base64 (coreutils).