dovresti usare le ricerche fulltext. La tabella deve essere di tipo myisam e devi definire un indice per poter fare le query.

Qui trovi un articolo in italiano
http://www.codicefacile.it/tutorials...erca_full-text
e qui il manuale
http://dev.mysql.com/doc/refman/4.1/...xt-search.html

una volta definito l'indice (nel mio esempio su 2 campi ma possono essere di più) dovresti fare una query del genere

select * from tabella where match(campo1,campo2)
against ('+cane +pluto' in boolean mode)

questa query restituisce i record solo se entrambe le parole sono presenti (come hai chiesto tu).
Poi ci sono un sacco di varianti.