Are CA authorised to sign a PGP Certificate?
I have a public/private PGP key pair used to sign emails.
When someone receives a message, he obviously has no way to check that the message was ~really~ signed by me without having received my public key before by other means. Is there a way to remedy that by having my public key signed by a CA?
Your public key can be 'signed' by any other private key you like. However, your recipient's issue will be how to trust the signer i.e. the burden of trusting your public key's origin has now shifted to the burden of trusting the signer's public key origin so not much has changed.
A 'CA' is a vague term. If you mean a SSL chain CA (as in browsers certification authority) then various CA's have their public key hard coded into the browser on installation and this removes the need to verify the signer's public key with a third party. PGP and similar encryption schemes don't work like this for a host of reasons but mostly because signing individual keys would be prohibitively complex and restrictive (think how complex/long the process is to have a signed SSL cert for a website for example, now multiply this with all of the PGP certs out there!)
PGP certificate trusting working on a web of trust i.e. the recipient needs to have some 'trusted' public keys pre installed on their keychain that have been marked as trusted by them usually by some side channel (phone someone up and check the key fingerprint for example). If your recipient does not have a trusted public key for someone you are using to sign your public key then they need to check the key with you by some other channel e.g. calling you and asking you to identify it by fingerprint etc. or to download it from a trusted third party keystore where the keystore has a verification mechanism. So, get your public key signed by as many trusted keyholders as you can and hope your recipient has a trusted corresponding signed public key, or call them for the first key installed into their keyring and confirm the fingerprint. Once installed and trusted on their keyring you are good to go without further trust issues.