If you want to send a custom HTTP Header (not a SOAP Header) then you need to use the HttpWebRequest class the code would look like:
HttpWebRequest webRequest = (HttpWebRequest)WebRequest.Create(url);
webRequest.Headers.Add("Authorization", token);
You cannot add HTTP headers using the visual studio generated proxy, which can be a real pain.