Great question. I'll answer it in several parts.
Which Keys does Alice send?
There are two cryptographic operations that Alice may want to do: encryption/decryption, and signing/validation. You can either use the same keypair for both, or have two separate pairs of keys.
1 keypair method:
Here Alice would sign outgoing messages, and decrypt incoming messages with the same private key. Bob would validate the signature on her outgoing messages, and encrypt messages for her using the same public key.
2 keypair method:
Here Alice would have a
(signing_private_key, validation_public_key) keypair, and a separate
(decryption_private_key, encryption_public_key) keypair.
In both cases she only sends the
public keys to the Certificate Authority (CA) to be made into certificates. The
private keys are private, she never shares them, they never leave her machine, they never become certificates.
How does the Certificate Authority (CA) trust Alice?
There are several trust models that different organizations use. Many large companies / government departments operate their own CAs for internal email, file storage, etc. In these cases when someone is hired they are issued digital certificates along with their ID badge, parking permit, etc. We trust that Alice is who she claims to be because she's sitting right in front of the Security Officer issuing the ID.
For web certificates like SSL establishing trust is little more complicated. The CA/Browser Forum has guidelines for CAs on how to verify the identity of applicants. Here is a long list of guidelines. The common forms that most CAs offer are Domain Validated (DV) and Extended Validation (EV) SSL certificates.
Domain Validated (DV) certs
This basically asks you for an email address and a person's name along with the web domain that you want a cert for. It does a
whois lookup on the domain to make sure that the name and email you provided matched the domain's registration information. Additionally they can send a confirmation to the email address to make sure that you control it. DV certs can be completely automated, and in fact, "On November 18, 2014, a group of companies and nonprofit organizations, including the Electronic Frontier Foundation, Mozilla, Cisco, and Akamai, announced "Let's Encrypt", a new nonprofit certificate authority that plans to provide free TLS certificates" (wikipedia).
Extended Validation (EV)
The CA/Browser Forum specifies criteria for issuing EV certs, these all require a human in the loop, and relate to how stringently the identity of the applicant organization is researched. Having a phone call between the CA and the applicant is a basic requirement. Often documents are signed, and a face-to-face meeting can even be required before the CA will issue an EV cert. The level of validation that was performed will be included in the certificate to increase its public trustworthiness, consequently issuing CAs charge more for higher quality EV certs.
Many issuers also offer variations on the SSL cert wich don't fall into either the DV or EV categories. For example GlobalSign also offers Organization Validation (OV) as an intermediate category. Entrust offers many different types of certs depending on the network structure and software systems being used by the applicant.