PEAR's Mail_Mime package is what you're after here.
Once you've set your message up, adding an attachment is as simple as:
$mime = new Mail_mime("\n");
$mime->setTXTBody($msg_text);
$mime->setHTMLbody($msg_html);
// Add gif as attachment to mail
$mime->addAttachment("/path/to/image/smile.gif", "image/gif");
$body = $mime->get();
$headers = $mime->headers($headers);
$mail->send("joe@bloggs.com", $headers, $body);
If you're looking for your logo to display in a particular place in the email - rather than solely as an attachment - you can do the following:
// In your message html:
<img src='logo.gif' alt='Our logo' />
// PHP:
$mime->addHTMLImage('/path/to/image/logo.gif');
This approach can have mixed results depending on your user's mail client, so before sending it out try testing your format on dummy gmail, yahoo and hotmail accounts.