Well, there's two parts to the equation:
- you could have a server certificate which the service uses to authenticate itself to the clients (to prove it's really the service it claims to be)
- you could have a client certificate which the client needs to prove its identity to the server
Which are you interested in?
Typically, if you have a server/service certificate, the client will either "know" the server's public key (it could be installed in the client's certificate store, e.g. by an installation program or by downloading and installing it), or it will inquire about the server's certificate at the time the proxy gets created and stores the server's public key in the local client config file for later use. This config will then again be installed with the app on the client.
If the client wants to authenticate itself against the service, it will definitely need to have its client certificate installed locally on the client machine's cert store.
I'd recommend checking out the WCF Security Guidance - it's a great resource, and they can explain how to do certain scenarios much better than I can!
On a all-Windows environment with everyone in the same domain, this seems like a bit of overkill - why not just use the built-in, Windows-provided credentials? That would be a lot easier, I would think.
Marc