Использовать
Ajax (асинхронный запрос к серверу) или, если используется jQuery, то его один из методов асинхронного запроса, который отправляет на север введенный адрес.
Запрос можно производить или по потере фокуса полем, или при отправлении формы.
На стороне сервера делаем запрос:
'SELECT 1 FROM table WHERE mail="' . mysql_real_escape_string($_POST['mail']) . '"'
//если используется mysqli или PDO, то и запрос короче будет
и возвращаем число полученных рядов.
Если такого адреса нет, значит клиенту будет возвращен 0, иначе 1.
Останется принять решение - вывод сообщения или принять форму.
Или нужен конкретный пример? Тогда показывайте свой код, указывайте используете ли jQuery.