How do I embed an image into CiviMail messages?
If you are referring to embedding images in the body of the email, yes, that is entirely possible in CiviMail.

Using the WYSIWYG editor, you can embed images. There is an image icon on the toolbar to do this.  The images will be stored on your server and can be referenced in the HTML email.  (Of course you could optionally just include the image hosted at a different URL as well.)  

You could theoretically embed the byte stream of an image, though I don't know why you would want/need this.  

If you are referring to attaching the images as attachments that is possible too.  Check the Attachments section when you are defining the email in CiviMail.