According to the Help menu on my Outlook:
You must use Microsoft Office Word 2003 as your e-mail editor when sending signatures with pictures or logos.
In the main Outlook window, on the Tools menu, click Options, and then click the Mail Format tab.
Under Message format, in the Compose in this message format list, click the message format that you want to use the signature with.
Under Signature, click Signatures, and then click New.
In the Enter a name for your new signature box, type a name.
Under Choose how to create your signature, select the option you want.
Click Next.
Click Advanced Edit.
When the dialog box appears cautioning you that an editor not part of Microsoft Office Outlook will open, click Yes.
Design your signature. When you are ready to insert a picture or logo, on the Insert menu, point to Picture, and then click From File.
Note If you are designing your signature in Word, make sure that you press SHIFT+ENTER at the end of each line of text. If you press only ENTER, Outlook inserts your signature so that the recipient sees your signature in double-spaced format.
Close the advanced editor, making sure that you click Yes to save your changes.
When you finish editing the new signature, click OK.