This is an important point, and a CA will have a Certificate Policy (or Practice) Statement (CPS) explaining how they do it. Typically this is available on the CA's Web site for anyone to read.
This check is what anchors electronic communications to the real world. Typically it involves the entity, or its representatives if it is an organization, actually presenting themselves in person to the CA, with proof of identity. If this is not practicable because entities wanting certification are geographically wide-spread, the CA will have Registration Authorities, local branches that carry out the in-person checks and then forward approval to the central CA.
Again, the RA uses a server which is itself known as the RA. The connection between the RA and CA is likely to be an electronic one - the RA notifies its approval to the CA, which then issues the certificate. At both levels, though, there are likely to be actual human beings making the decisions to recognize the proofs of identity, and to grant the certificates.
If the entities wanting certification are too widespread even for RAs to be within reach of them all, then the CA may use notaries - individuals authorized to check identification in person and forward the details to the CA or one of its RAs.
All these policies should be detailed in the CA's CPS - this document and the policies it describes are as important a part of a PKI as the SSL technology itself.