Neste tutorial, explico como RECEBER corretamente dados com caracteres especiais como cedilha e acentos. Para enviar dados acentuados corretamente, leia esta solução (no sub-capítulo "Recebendo os dados (no PHP)".
Publicado também no meu blog.

Explicações e lero-lero iniciais:

O XMLHttpRequest, a criança por trás do ajax, trabalha no padrão UTF-8 por default, tanto pra enviar dados quanto pra receber. Isso vem do próprio browser mesmo. Nos primórdios da internet, o Tim Berners-Lee ainda não estava tão preocupado com a internacionalização do HTML. Este esforço só começou a acontecer em novembro de 1995, depois da formação da W3C, onde visavam extender as capacidades do HTML 2 (falarei disso no histórico do HTML que estará presente no meu TCC). Por este motivo o Ajax dá vários problemas com nossos caracteres.

Para tentar resolver este problema, temos a forma correta é é o uso de HTML Entities, porém isto nem sempre é possível.
Para contornar já ví muitas viagens, que usam gambiarras de encode, escape, etc. nos scripts do lado do servidor (asp, php, jsp, etc). Uma complicação só!!!

Em minhas pesquisas, descobri que a forma correta de renderizar nosso português é simplesmente usando o charset ISO-8859-1 e não o UTF-8. Simples assim. Você deve enviar cabeçalhos pro navegador, informando que você usará ISO-8859-1. Agora é só você configurar seu servidor pra servir ISO-8859-1 por padrão, se você tiver acesso a isto OU indicar o charset no início do seu script server side, com apenas 1 (uma) linha de código!! -- Me perdoem o "servidor pra servir", é que não achei outros termos.

"Chega de enrolação mico, e mostra logo comé que faz."

1) Caso você não possa alterar as configurações de caracteres do servidor:

É só adicionar a seguinte linha no começo da página que será retornada para o AJAX:

• ASP: <% Response.Charset="ISO-8859-1" %>
• PHP: <?php header("Content-Type: text/html; charset=ISO-8859-1",true) ?>
• JSP: <%@ page contentType="text/html; charset=ISO-8859-1" %>

2) Caso você tenha como alterar as configurações de caracteres do servidor:

Adicione o charset ISO-8859-1 como charset default do seu servidor.

Caso seu servidor seja o Apache, adicione (ou altere) a seguinte linha no http.conf:
(agradecimentos ao reges (nao_sei) e ao mestre fyoda)


Observações finais:

• Lembre-se: Se for possível trabalhar com os HTML Entities, trabalhe!! Você pode pesquisar funções de conversão para html entities na referência da sua linguagem.
• Este script é apenas para resolver os problemas da recepção dos dados acentuados. Para os problemas de envio, leia esta solução (no sub-capítulo "Recebendo os dados (no PHP)". ou este tutorial.
• Se voce quer carregar um arquivo xml ou html simples que não usa linguagem server side, talvez voce consiga resolver o problema da acentuação usando só o a tag meta, eu testei porém não consegui. Provavelmente porque os METAs e headers já foram carregadas no início da página principal.
• Outra forma é usar o responseXML ao invés do responseText pois, de acordo com a mozilla.org, o responseXML interpreta corretamente outros caracteres e não apenas o UTF-8. (agradecimentos ao Ederson)
• O problema também pode estar sendo causado por banco de dados. Se for isto, verifique as configurações de linguagem de seu banco de dados e prefira utilizar o ISO-8859-1.