Les "credentials" sont ajoutées dans le header de la requête WEB. Ainsi pour se faire, il faut construire une classe héritant de SoapHeader 
public class UserCredentials : SoapHeader
{
    public string UserName;
    public string Password;
}
Il faut par après implémenter le webservice ;-). Pour les méthodes ou il faut ajouter les credentials, il faut spécifier un attribut [SoapHeader("CustomCredentials")]. 
[WebService(Namespace = "http://tempuri.org/")]
[WebServiceBinding(ConformsTo = WsiProfiles.BasicProfile1_1)]
public class SecureWebService : WebService
{
    public UserCredentials CustomCredentials
    {
        get { return m_userCredentials; }
        set { m_userCredentials = value; }
    }

    public SecureWebService ()
    {

        //Uncomment the following line if using designed components 
        //InitializeComponent(); 
    }

    [WebMethod]
    [SoapHeader("CustomCredentials")]
    public string HelloWorld()
    {
        if (null != CustomCredentials)
        {
            return "Hello World " + CustomCredentials.UserName;
        }

        return "Not logged";
    }

    [WebMethod]
    public string HelloWorld2()
    {
        if (null != CustomCredentials)
        {
            return "Hello World " + CustomCredentials.UserName;
        }

        return "Not logged";
    }

    private UserCredentials m_userCredentials;
}
Il ne reste plus qu'a appeler ce webservice depuis du code client en spécifiant le login pass ... On voit ainsi que la méthode "HelloWorld" reçoit les credentials au contraire de "HelloWorld2"... 
localhost.SecureWebService web = new ConsoleApplication1.localhost.SecureWebService ();
web.UserCredentialsValue = new ConsoleApplication1.localhost.UserCredentials();
web.UserCredentialsValue.UserName = "Admin";
web.UserCredentialsValue.Password = "Admin";
string result = web.HelloWorld();
Console.Out.WriteLine(result);
result = web.HelloWorld2();
Console.Out.WriteLine(result);