Assuming you're using EXM 3.3 (or later) this can be done by overriding the dispatchprovider. You'll find this element under /sitecore/exm/eds/dispatchManager in the configuration (Sitecore.EDS.Providers.CustomSMTP.config or Sitecore.EDS.Providers.Dyn.config) e.g.
<dispatchManager defaultProvider="default">
<providers>
<clear />
<add name="default" type="Sitecore.EDS.Providers.CustomSmtp.DispatchProvider, Sitecore.EDS.Providers.CustomSmtp">
<param ref="exm/eds/connectionPool" />
<param ref="exm/eds/environmentIdentifier" />
</add>
</providers>
</dispatchManager>
You'll need to override the SetMessageHeaders method e.g.
protected override void SetMessageHeaders(EmailMessage message)
{
base.SetMessageHeaders(message);
message.Headers.Set("Your-Header-Name", "Your-Value");
}
In EXM 3.4 and later, this configuration element has changed and is now called
<dispatchProvider defaultProvider="default">
<providers>
<clear />
<add name="default" type="Sitecore.EDS.Providers.CustomSmtp.DispatchProvider, Sitecore.EDS.Providers.CustomSmtp">
<param ref="exm/eds/connectionPool" />
<param ref="exm/eds/environmentIdentifier" />
</add>
</providers>
</dispatchProvider>