1. Ten a la mano el nombre del usuario (la variable).
2. Crea una consulta antes de insertar el usuario
Código PHP:
$consulta="SELECT * FROM tabla WHERE usuario='$usuario'";
3. En caso de no haber consulta se inserta el nuevo usuario (INSERT INTO ...)
4. En el caso que haya un usuario registrado, solo pones un echo que diga lo mismo, Usuario previamente registrado.
Espero haberme explicado