Verificar y devolver mensaje

[urgido]

Quisiera saber como me conecto a una base de datos mediante un formulario para hacer lo siguiente:

1.- Conectarme a una base de datos, posteriormente a una table y por último a un campo llamado USUARIOS.

2.- Verificar si dentro de ese campo el contexto dado en el formulario existe, si existe Imprimira "USUARIO YA EXISTENTE" de lo contrario Imprime "NO SE ENCONTRÓ USUARIO".

Ahora bien por el otro lado esto es por que me ayudaron a hacer un sistema de registro de usuarios el cual esta muy "simple" y quiero darle lo básico, también tengo otro problemita respecto al cambio de contraseña, cuando un usuario se registra le he puesto una función llamada "frase" la cual le servirá en caso de que olvide su contraseña pero... quisiera saber como le hago para hacer algo similar como lo que les he puesto arriba nada más que en este caso el formulario enviaría el contexto a la misma base de datos, a la misma tabla pero al campo llamado "FRASE" y si la FRASE coindide con el USUARIO entonces se procede a pasar a la página recuperar contraseña(en este caso sería rec_pass.php de lo contrario los deja en la misma página pero se imprimiría "NO COINCIDEN LOS CAMPOS".

Yo sé que esto no es fácil pero quién me desee ayudar se lo agradecería. Saludos.