mm en todos los campos de tus tablas?
Bueno, .. sería recomendable que limitases un poco el tema .. sobre todo por qué no sé si todos tus campos son del mismo tipo (numéricos y alfanuméricos), con los campos de tipo "fechas" (DATE .. etc) tendras que adaptar lo que el usuario seleccione/use para darle el formato adecuado a un campo por ejemplo "DATE".
El resto no es más que consultas SQL a tu BD .. eso sí .. te ayudaría usar busquedas tipo "FULL TEXT" (para obtener los resultados ordenados por coincidencias de lo que andas buscando ..)
Si pese a eso quieres "buscar" en toda tu BD .. podrías usar algún script ya hecho (o mejor classe) para tal fin que .. lo que hacen básicamente es "leer" el nombre de tus BD .. de tus tablas .. de tus campos para aplicar un "SELECT" SQL a todo lo que encuentre:
Podrias ver en:
http://phpclasses.promoxy.com/browse/class/10.html
Un saludo,