Note! This section assume you have a basic familiarity with modern cryptography, S/MIME, various PKCS standards, OpenSSL and so on.
The S/MIME support in Message (and MML) require OpenSSL. OpenSSL performs the actual S/MIME sign/encrypt operations. OpenSSL can be found at http://www.openssl.org/. OpenSSL 0.9.6 and later should work. Version 0.9.5a cannot extract mail addresses from certificates, and it insert a spurious CR character into MIME separators so you may wish to avoid it if you would like to avoid being regarded as someone who send strange mail. (Although by sending S/MIME messages you've probably already lost that contest.)
To be able to send encrypted mail, a personal certificate is not
required. Message (MML) need a certificate for the person to whom you
wish to communicate with though. You're asked for this when you type
C-c C-m c s. Currently there are two ways to retrieve this
certificate, from a local file or from DNS. If you chose a local
file, it need to contain a X.509 certificate in PEM format.
If you chose DNS, you're asked for the domain name where the
certificate is stored, the default is a good guess. To my belief,
Message (MML) is the first mail agent in the world to support
retrieving S/MIME certificates from DNS, so you're not
likely to find very many certificates out there. At least there
should be one, stored at the domain simon.josefsson.org. LDAP
is a more popular method of distributing certificates, support for it
is planned. (Meanwhile, you can use ldapsearch from the
command line to retrieve a certificate into a file and use it.)
As for signing messages, OpenSSL can't perform signing operations
without some kind of configuration. Especially, you need to tell it
where your private key and your certificate is stored. MML
uses an Emacs interface to OpenSSL, aptly named smime.el, and it
contain a custom group used for this configuration. So, try
M-x customize-group RET smime RET and look around.
Currently there is no support for talking to a CA (or RA) to create your own certificate. None is planned either. You need to do this manually with OpenSSL or using some other program. I used Netscape and got a free S/MIME certificate from one of the big CA's on the net. Netscape is able to export your private key and certificate in PKCS #12 format. Use OpenSSL to convert this into a plain X.509 certificate in PEM format as follows.
$ openssl pkcs12 -in ns.p12 -clcerts -nodes > key+cert.pem
The key+cert.pem file should be pointed to from the
smime-keys variable. You should now be able to send signed mail.
Note! Your private key is now stored unencrypted in the file,
so take care in handling it. Storing encrypted keys on the disk are
supported, and Gnus will ask you for a passphrase before invoking
OpenSSL. Read the OpenSSL documentation for how to achieve this. If
you use unencrypted keys (e.g., if they are on a secure storage, or if
you are on a secure single user machine) simply press RET at
the passphrase prompt.