¿Protoype o JQuery?
JQuery, sin duda.
La manera de trabajar con JQuery es mas sólida, incluye clases que permiten efectos visuales (para tenerlos en Prototype hay que usar script.aculo.us), pesa sólo 19KB frente a 126KB de Prototype, tiene un mayor número de actualizaciones y está mejor documentado.
Esas son mis razones para escoger JQuery siempre que tengo que usar un framework AJAX. De todas maneras debo decir que Prototype es un buen framework y su uso está muy extendido.
AJAX

AJAX es uno de los pilares de la Web 2.0. No es un lenguaje de programación, no es un framework, no es un entorno de desarrollo, no es una nueva tecnología. AJAX es tan solo una metodología aplicada sobre JavaScript que nos permite cargar partes de un documento XML dinámicamente. Como todo el código JavaScript, AJAX se ejecuta del lado del cliente, en el navegador.
En el modelo clásico de programación web, la comunicación es síncrona. El cliente solicita un recurso y este es servido por el servidor, una vez finalizado el proceso se puede solicitar un nuevo recurso. Mediante AJAX podemos efectuar varias solicitudes de recursos a la vez, antes de recibir la respuesta del servidor, que serán cargadas según se vayan recibiendo, lo que se conoce como comunicación asíncrona.
A la hora de desarrollar, esta técnica nos permite que unas partes de la web cambien en función de otras partes o de una situación dada, acercando la programación web a la programación de escritorio.
AJAX se basa en la interfaz JavaScript XMLHttpRequest. Pueden desarrollarse clases y métodos usando esta interfaz para usar AJAX en nuestros desarrollos no obstante, es mejor no reinventar la rueda. Existen frameworks AJAX muy optimizados y bien depurados que es recomendable usar si queremos dar dinamismo a nuestros desarrollos. Entre ellos dos que recomiendo, y en los que me detendré mas adelante en este blog son Prototype y JQuery.