Можно использовать класс SoapHeader. Нужно добавить внутренний класс в класс сервиса, унаследовав его от SoapHeader, например, так
public class WebService1 : WebService
{
...
public AuthSoapHeader authSoapHeader;

public class AuthSoapHeader : SoapHeader
{
private String login = String.Empty;
private String password = String.Empty;

public String Login
{
get
{
return login;
}
set
{
login = value;
}
}

public String Password
{
get
{
return password;
}
set
{
password = value;
}
}
}

...
}
И перед методом сервиса добавить
[WebMethod(EnableSession = true), SoapHeader("authSoapHeader")]
В самом методе использовать объект authSoapHeader.
Для того, чтобы передать его при вызове сервиса
WebService1 service =
new WebService1();
AuthSoapHeader authSoapHeader = new AuthSoapHeader();
authSoapHeader.Login = "login";
authSoapHeader.Password = "password"
service.AuthSoapHeaderValue = authSoapHeader;
service.Method()