From a high level perspective, three things have to happen:
The client has to prove that it is the proper owner of the client certificate. The web server challenges the client to encryptsign something with its private key, and the web server validates the response with the public key in the certificate.
The certificate has to be validated against its signing authority This is accomplished by verifying the signature on the certificate with the signing authority's public key. In addition, certificate revocation lists (CRLs) are checked to ensure the cert hasn't been blacklisted.
The certificate has to contain information which designates it as ana valid user of the web service. The web server is configured to look at specific items in the certificate (typically the subject field) and only allow certain values.