Se trata de generar un mail en formato "multiparte" .. con una parte para el texto plano y otra para HTML + otra con las imagenes en formato MIME ..
En la parte HTML haces llamadas a las imagenes incrustadas via un:
<IMG SRC="cid:img1">
con eso haces la referencia a la imagine incrustada ...
Para ayudarte en esta tarea puedes usar una classe (objeto en PHP) que dicen q va bastante bien:
http://phpmailer.sourceforge.net/
Esta classe (y similares) ya se encarga de colocarte las cabeceras HTTP necesarias y de adjuntar la imagen o incluso archivo adjunto en su formato MIME ..
Esta classe hace bastantes "virgerias" .. entre otras:
Usa SMTP o el MTA (sendmail o servidor q use la configuración de PHP) .. envia HTML/texto plano con imagenes incrustadas y archivos adjuntos ...
Y lo mejor .. está bien documentada.
Un saludo,