Well, I eventually figured this out. Here is a method that will create a mail message, store it as a draft, add the attachment and then send the email. Hope this helps someone out there who wasn't able to find a good example like me.
In my example, I'll only be sending excel files which is why the content type is set like it is. This can, obviously, be changed to support any type of file attachment.
For your reference, the variable esb is a class level variable of type ExchangeServiceBinding.
Edit
I should also note that in this example, I'm not checking the response types from the exchange actions for success or failure. This should definitely be checked if you care to know whether or not your calls to EWS actually worked.
public void SendEmail(string from, string to, string subject, string body, byte[] attachmentAsBytes, string attachmentName)
{
//Create an email message and initialize it with the from address, to address, subject and the body of the email.
MessageType email = new MessageType();
email.ToRecipients = new EmailAddressType[1];
email.ToRecipients[0] = new EmailAddressType();
email.ToRecipients[0].EmailAddress = to;
email.From = new SingleRecipientType();
email.From.Item = new EmailAddressType();
email.From.Item.EmailAddress = from;
email.Subject = subject;
email.Body = new BodyType();
email.Body.BodyType1 = BodyTypeType.Text;
email.Body.Value = body;
//Save the created email to the drafts folder so that we can attach a file to it.
CreateItemType emailToSave = new CreateItemType();
emailToSave.Items = new NonEmptyArrayOfAllItemsType();
emailToSave.Items.Items = new ItemType[1];
emailToSave.Items.Items[0] = email;
emailToSave.MessageDisposition = MessageDispositionType.SaveOnly;
emailToSave.MessageDispositionSpecified = true;
CreateItemResponseType response = esb.CreateItem(emailToSave);
ResponseMessageType[] rmta = response.ResponseMessages.Items;
ItemInfoResponseMessageType emailResponseMessage = (ItemInfoResponseMessageType)rmta[0];
//Create the file attachment.
FileAttachmentType fileAttachment = new FileAttachmentType();
fileAttachment.Content = attachmentAsBytes;
fileAttachment.Name = attachmentName;
fileAttachment.ContentType = "application/ms-excel";
CreateAttachmentType attachmentRequest = new CreateAttachmentType();
attachmentRequest.Attachments = new AttachmentType[1];
attachmentRequest.Attachments[0] = fileAttachment;
attachmentRequest.ParentItemId = emailResponseMessage.Items.Items[0].ItemId;
//Attach the file to the message.
CreateAttachmentResponseType attachmentResponse = (CreateAttachmentResponseType)esb.CreateAttachment(attachmentRequest);
AttachmentInfoResponseMessageType attachmentResponseMessage = (AttachmentInfoResponseMessageType)attachmentResponse.ResponseMessages.Items[0];
//Create a new item id type using the change key and item id of the email message so that we know what email to send.
ItemIdType attachmentItemId = new ItemIdType();
attachmentItemId.ChangeKey = attachmentResponseMessage.Attachments[0].AttachmentId.RootItemChangeKey;
attachmentItemId.Id = attachmentResponseMessage.Attachments[0].AttachmentId.RootItemId;
//Send the email.
SendItemType si = new SendItemType();
si.ItemIds = new BaseItemIdType[1];
si.SavedItemFolderId = new TargetFolderIdType();
si.ItemIds[0] = attachmentItemId;
DistinguishedFolderIdType siSentItemsFolder = new DistinguishedFolderIdType();
siSentItemsFolder.Id = DistinguishedFolderIdNameType.sentitems;
si.SavedItemFolderId.Item = siSentItemsFolder;
si.SaveItemToFolder = true;
SendItemResponseType siSendItemResponse = esb.SendItem(si);
}