The IMAP protocol doesn't make it possible to modify a message at the IMAP server. However, you can download the message, modify it, and then optionally re-upload it (in case you would like to archive it on the IMAP server).
For information on how to download messages, please see IMAP - message operations and check out the ImapDownloader sample that comes with Rebex Secure Mail install package.
To add a header to a downloaded message, the most efficient method would be to use the low-level
MimeMessage class with
var message = new MimeMessage();
message.Options = MimeOptions.OnlyParseHeaders;
message.Headers.Add("X-My-Custom-Header", "Custom header value");
(Although, for more complex operations, the high-level
MailMessage class is usually more suitable.)