Hola:
Creo que primero deberías informarte sobre como se implementa esta tecnología, pero a grandes rasgos...
<input type="text" name="nombre" onchange="validarNombre(this.value); mostrarEsperaNombre()"...
En mostrarEsperaNombre() mostrar ese gif que te he comentado, y en validarNombre, una llamada así:
Ajax.open("GET", "valida.php?nombre=" + nombre, true);
en valida.php, hacer la consulta:
select nombre from tabla where nombre = '$nombre'";
Y si el num_rows es cero está disponible, así que provocas la salida que luego proceses con Ajax...
Pero, todo esto necesita de unos conocimientos básicos que antes deberías tener.
Saludos