How can I configure WCF to use x509 certificates over the internet?

I'd recommend reading the WCF Security guidance from Microsoft

This deals with this scenario as well as many others

http://www.codeplex.com/WCFSecurityGuide/

edit: now at https://archive.codeplex.com/?p=wcfsecurityguide

The following steps are a guide to get you started:

1) Firstly, you need a Root Authority to generate your client and server certificates. You can either use an external Authority Provider (e.g. Verisign) or you can generate your own using something like Microsoft Certificate Server.

To generate a development Root Authority certificate you can use the "makecert" tool that comes with Visual Studio, e.g.

makecert -n "CN=MyRootCA" -r -sv RootCA.pvk RootCA.cer

2) You then need to request/generate your client and server certificates. Both types of certificates can be installed as local machine certificates and both need to be signed using the same root authority. You can request client certificates from a Microsoft Certificate Server's web interface, e.g. http://mycertserver/certsrv.

To generate a development client certificate for each machine you can use "makecert" again. Note that the client certificates are signed with development Root Authority certificate created in step 1.

makecert -pe -n "CN=MyCert" -ss my -sky exchange -sk MyCert 
         -iv MyRootCA.pvk -ic MyRootCA.cer -sr localmachine MyCert.cer

This will install the certificate on the machine on which the command is run, into the Personal certificates folder in the Local Machine store.

In order for the server to trust the client certificates you will need to install the development Root Authority certificate in the server's Trusted Root Certificate Authorities store (use the mmc Certificates snap-in to do this). The clients should also have the root certificate installed in the same way so that they trust their own certificates.

3) Configure you WCF service to require client authentication using a certificate (e.g. via the web.config).

<services>
  <service
    name="TestService"
    behaviorConfiguration="wsHttpCertificateBehavior">
    <endpoint name="TestEndPoint"
      address=""
      binding="wsHttpBinding"
      bindingConfiguration="wsHttpEndpointBinding"
      contract="TestService.IMyContract">
      <identity>
        <dns value=""/>
      </identity>
    </endpoint>
    <endpoint address="mex" binding="mexHttpsBinding" contract="IMetadataExchange"/>
  </service>
</services>

<bindings>
  <wsHttpBinding>
    <binding name="wsHttpEndpointBinding">
      <security mode="Message">
        <message clientCredentialType="Certificate"/>
      </security>
    </binding>
  </wsHttpBinding>
</bindings>

<behaviors>
  <behavior name="wsHttpCertificateBehavior">
    <serviceMetadata httpGetEnabled="false" httpsGetEnabled="true"/>
    <serviceCredentials>
      <clientCertificate>
        <authentication 
          certificateValidationMode="PeerOrChainTrust" 
          revocationMode="NoCheck"/>
      </clientCertificate>
      <serverCertificate findValue="CN=MyCert"/>
    </serviceCredentials>
  </behavior>
</behaviors>

4) Now configure the caller (e.g. via the app.config).

<client>
  <endpoint name="wsHttpBinding"
    address="https://localhost/TestService/TestService.svc"
    binding="wsHttpBinding"
    bindingConfiguration="wsHttpBinding"
    behaviorConfiguration="wsHttpCertificateBehavior"
    contract="TestService.IMyContract">
    <identity>
      <dns value="MyCert"/>
    </identity>
  </endpoint>
</client>

<bindings>
  <wsHttpBinding>
    <binding name="wsHttpBinding">
      <security mode="Message">
        <message clientCredentialType="Certificate"/>
      </security>
    </binding>
  </wsHttpBinding>
</bindings>

<behaviors>
 <endpointBehaviors>
  <behavior name="wsHttpCertificateBehavior">
    <clientCredentials>
      <clientCertificate findValue="MyCert" storeLocation="LocalMachine"/>
      <serviceCertificate>
        <authentication 
          certificateValidationMode="PeerOrChainTrust" 
          revocationMode="NoCheck" 
          trustedStoreLocation="LocalMachine"/>
      </serviceCertificate>
    </clientCredentials>
  </behavior>
 </endpointBehaviors>
</behaviors>