Hola:
Pues la consulta mysql sería algo así:
$sql = "select usuario from $tablaUsuarios where nombre = '$nombre'";
...
$existentes = mysql_num_rows; // inexistente
Y la parte javascript
:
ajax = new objetoAjax();
ajax.open("GET", url + "?nombre=" + nombre, true);
ayax.onreadystatechange = function() {
if (ajax.readyState == 4) // leer resultado...
}
ajax.send(null);
... puedes activar el botón submit si no existe el usuario...
Saludos