con PHP es fácil, pero con AJAX xd no sé como se haría, lo siento, si quieres PHP:
include('config.php');
$comprobamos =mysql_fetch_array(mysql_query("SELECT * FROM usuarios WHERE dni='".$_POST['dni']."'", $link));
if($comprobamos == $_POST['dni']){
echo 'Tu dni ya está registrado en nuestra base de datos';
}else{
echo 'registro permitido';
}
La comprobación daría null si no existe, entonces registraría, pero en caso de que no nea null, estamos seguros que existe ya que en la consulta le decimos WHERE dni, bueno no sé por que lo explico, lo deberías saber, aparte que mis explicaciónes són catastróficas.