Treww, читай RFC по части MIME multipart/mixed.
Составить письмо, включая основной заголовок и закоголовки для частей письма, закодировать base64 где надо - все это "вручную".
Поройся в сети - кто-то уже написал библиотеку для формирования письма с атачами.
Одна из них - mime_mail:
http://www.yandex.ru/yandsearch?text=class+mime_mail&stype=wwwMOPO3, поправка: subject рекомендуется передавать не самостоятельным параметром, а в списке заголовков после content-type. Это для того, чтобы гарантировать объявление кодировки раньше, чем любого не-ASCII текста. При этом второй параметер mail() нужно задать пустой строкой.