Basicamente lo que tienes es que jugar un poquito con la consulta.
Primero separas la cadena entrada por el usuario en palabras separadas (Si quieres puedes hacer un filtro para eliminar las palabras mas comunes).
Luego dependiendo de el numero de palabras, vas creando tu consulta.
Un ejemplo con 2 palabras seria:
SELECT * FROM tabla WHERE ((campo1 LIKE %hola% OR campo2 LIKE %hola% OR campo3 LIKE %hola%) OR (campo1 LIKE %mundo% OR campo2 LIKE %mundo% OR campo3 LIKE %mundo%))
Te dejo un tutorial muy bueno:
http://www.roscripts.com/PHP_search_engine-119.html
*Esta en ingles
Sino sabes ingles trata usando el traductor de Google o pedirle a un amigo que te ayude.