It sounds like the Java webservice is using SSL TLS protocol instead of the old school SSL protocol. You don't need to "encrypt the certificate username and password in the header". I don't now where you heard that. If its a regular certificate that is part of Java's default cacerts keystore then Java already has the password built into it.
In the case that i is a self signed cert (on the webservice end) you might need to somehow tell C# to trust self-signed cert. Also, the "credentials" that you are referring to are not the username + password, but is instead just the private key payload.