The answers above are so wrong! DO NOT add custom headers. Judging from your sample xml, it is a standard WS-Security header. WCF definitely supports it out of the box. When you add a service reference you should have basicHttpBinding binding created for you in the config file. You will have to modify it to include security element with mode TransportWithMessageCredential and message element with clientCredentialType = UserName:
<basicHttpBinding>
<binding name="usernameHttps">
<security mode="TransportWithMessageCredential">
<message clientCredentialType="UserName"/>
</security>
</binding>
</basicHttpBinding>
The config above is telling WCF to expect userid/password in the SOAP header over HTTPS. Then you can set id/password in your code before making a call:
var service = new MyServiceClient();
service.ClientCredentials.UserName.UserName = "username";
service.ClientCredentials.UserName.Password = "password";
Unless this particular service provider deviated from the standard, it should work.