O Edgar Muniz Berlinck já deu uma visão geral, e a resposta do OnoSendai descreve o protocolo muito bem, mas gostaria de complementar com a motivação por trás desse protocolo (e fazer algumas pequenas retificações).
Quando um cliente (digamos, Alice) se conecta a um servidor (Bob) através da internet, essa conexão é indireta - Alice manda a mensagem pra Charlie, que manda pra Dave, que manda pra Mallory que manda pra Bob. Bob responde pra Mallory, que repassa pra Dave, que manda pra Charlie que manda pra Alice. Nem sempre se sabe qual o caminho exato que os pacotes vão percorrer, nem se pode garantir com certeza que todos os nós são honestos. Como garantir que a comunicação entre Alice e Bob seja confidencial (ninguém no meio a veja), íntegra (ninguém no meio a altere) e autêntica (na outra ponta da comunicação tem de estar Bob, e não alguém se passando por Bob)?
A criptografia - originada há séculos no meio militar, e somente popularizada no meio civil após o surgimento da internet - busca resolver esse problema: mandar mensagens seguras por um canal de comunicação inseguro. Existem dois tipos de criptografia: simétrica (os dois pares compartilham um segredo) e assimétrica (um deles possui um segredo que o outro não possui). O SSL/TLS utiliza ambos: assimétrica para assegurar a autenticidade, e simétrica para a confidencialidade e integridade.
Respondendo então à sua primeira dúvida: há sim uma chave diferente a cada conexão - a simétrica, que é resultado do protocolo de "aperto de mão" (handshake) tal qual descrito por OnoSendai. Entretanto, o(s) par(es) de chaves assimétricas (chave pública e privada do servidor, e opcionalmente também do cliente) não mudam com frequência. Mas isso não é problema, pois a privada nunca é revelada, e a pública - como o próprio nome diz - não precisa ser mantida em segredo...
(Atualização: após uma releitura do handshake, percebo que há sim um par público/privado que é gerado a cada conexão e usado para transmitir a chave assimétrica. Uma "chave cifradora de chaves" - Key Encryption Key ou KEK. Entretanto, o par cuja chave pública está contida no certificado, esse sim não muda com frequência: sua validade típica é dois anos, e ela somente é usada para assinar, nunca pra cifrar.)
E como esse par de chaves (pública, privada) é usada para garantir a autenticidade? Em primeiro lugar, o servidor envia ao cliente sua chave pública. Eventualmente, ele assina algo com sua chave privada - provando ao cliente que ele é mesmo o "dono" da chave pública. Até aí tudo bem, mas como Alice pode ter certeza que a chave que ela recebeu dizendo vir de Bob veio mesmo de Bob? Aí entra um caso do ovo e da galinha:
Se Alice já conhece a chave pública de Bob (i.e. tem salvo no seu computador a chave de Bob associada à sua identidade - por exemplo, o domínio que pertence a Bob), então é tranquilo. Caso contrário, ela precisa que alguém de confiança faça intermédio nessa comunicação (como verificar a assinatura de Bob se Alice não tem nada pra comparar com ela?). Isso é feito através de um certificado. Um certificado é:
- Uma chave pública...
- ...associada a uma identidade (um nome)...
- ...e o par assinado por alguém de confiança.
Há mais de uma maneira de se fazer isso - Autoridades Certificadoras (CA), Redes de Confiança (Web of Trust), Notários, etc. Não sei te dizer quais o protocolo SSL/TLS suporta, mas o mais comum é o uso de Autoridades Certificadoras. Elas são, grosso modo, um conjunto de empresas cuja chave pública já vem embutida no software que você usa. Se você estiver usando o Firefox, por exemplo, pode verificar quem são elas consultando Ferramentas -> Opções -> Avançado -> Certificados -> Certificados (de novo) -> Autoridades
.
(Repare que a ICP-Brasil não está nessa lista... já notou que sempre que você tenta entrar em um site seguro do Governo o browser dá um alerta de certificado inválido?)
Se você tem por exemplo um website, e quer que ele esteja disponível de forma segura para o público em geral, não há muito o que fazer a não ser pagar para uma dessas empresas para verificar sua identidade e assinar seu certificado (criar o certificado é o de menos, qualquer um pode fazer). Levando em consideração que nem todo SO ou browser reconhece toda CA. Mas se tudo o que você quer é distribuir uma aplicação para um público restrito (digamos, algo que só será acessível aos funcionários da sua empresa) você também pode criar um Certificado Raiz - usado para assinar outros certificados - e instalá-lo manualmente no browser dos usuários. Evitando assim ter que pagar por esse serviço.
(Lembrando sempre que o meio de se distribuir esse certificado raiz tem de ser seguro. Ovo e galinha, lembra? Você poderia levar ele à mão, num pendrive por exemplo, mas para distribuir via internet você precisaria de novo da ajuda de alguém em quem você já confia...)
Fechando então, após a entrega e verificação do certificado (que é um processo relativamente lento, como apontado por OnoSendai, mas só da primeira vez, quando o certificado não está na cache), é necessário assegurar a autenticidade de Alice. Isso pode ser feito também via certificados, mas o mais comum é omitir essa etapa (posteriormente, o uso de um simples nome de usuário e senha diz ao site quem é o usuário - sem fazer parte do protocolo SSL/TLS). Após ambos estarem autenticados, usa-se criptografia simétrica - essa sim bastante rápida - para a comunicação normal.