aver, si es esto...
Código PHP:
$chekear = mysql_query("SELECT `mail` FROM `usuarios` WHERE `mail` = '$mail");
$chekear= mysql_num_rows($chekear);
if ($chekear>=1) {
echo "El email ya existe en la base de datos";
}
else
{
/// Aca el coodigo para insertar el mail en la base de datos
}