Bueno .. se hace gestionando las cabeceras del mail() (header) .. ahí le indicas que el mail es "multiparte" y la parte que es de "texto/plano" y la que es "HTML" ...
Yo para esas cosas suelo usar la classe:
PHP Mailer
http://phpmailer.sourceforge.net
Ademas de permitirte enviar un e-mail en texto plano y HTML a la vez te permite enviar archivos adjuntos, imagenes incrustadas en tus mails HTML y enviar por mail() de PHP, por SMTP o sendmail directo entre otras funcionalidades ...
En
http://pear.php.net también tienes mas classes para enviar y gestionar mails y sus cabeceras (incluidos los "MIME" formato ..)
Un saludo,