Usually a company that, for a fee, will issue a Public key certificate that states that the CA trusts that the owner of the public key contained in the certificate is who s/he represents to be. A CA is expected to check an applicants identity to match with the credentials on the certificate, so that the user can trust all certificates issued by a CA to belong to the people identified by it, and not to an imposter.
In large-scale deployments Alice may not be familiar with Bob's certificate authority (perhaps they each have a different company CA), so Bob's certificate may also include his CA's public key signed by a "higher level" CA2, which is presumably recognized by Alice. This process leads in general to a hierarchy of certificates.
See: Public key certificate, X.509, PGP, Certificate Revocation List, CAcert.