Both certificates should exist prior to the connection. They're usually created by Certification Authorities (not necessarily the same). (There are alternative cases where verification can be done differently, but some verification will need to be made.)
The server certificate should be created by a CA that the client trusts (and following the naming conventions defined in RFC 6125).
The client certificate should be created by a CA that the server trusts.
It's up to each party to choose what it trusts.
There are online CA tools that will allow you to apply for a certificate within your browser and get it installed there once the CA has issued it. They need not be on the server that requests client-certificate authentication.
The certificate distribution and trust management is the role of the Public Key Infrastructure (PKI), implemented via the CAs. The SSL/TLS client and servers and then merely users of that PKI.
When the client connects to a server that requests client-certificate authentication, the server sends a list of CAs it's willing to accept as part of the client-certificate request. The client is then able to send its client certificate, if it wishes to and a suitable one is available.
The main advantages of client-certificate authentication are:
You may be interested in Advantages of client certificates for client authentication? (on Security.SE).