En resumen se trata de usar SQL y generar la consulta adecuada atendiendo a las condiciones que quieras . .ya sea buscar en campos de una misma tabla (uno o varios a la vez) o en várias tablas simultaneamente .. etc... Todo es SQL (si hablamos de Base de datos) ..
Yo recomendaría como comenta Gux que primero te aclares con que "tipo" de buscador quieres (y te insisto que eso es taréa de SQL no de PHP en principio) y .. si no tienes claro como trabajar con formularios y obtener sus datos/filtrarlos/validarlos en PHP para luego usarlos y los condicionales de las sentencias SQL que vas a tener que componer y ejecutar sobre tu BD .. que, empieces por el principio.
Un saludo,
PD:
www.hotscripts.como puedes encontrar buscadores sobre Base de datos ya hechos de forma genérica (le dices poco más que las tablas que quieres buscar y los campos que quieras usar y el resto lo hacen ellos...)