Przede wszystkim musisz poczytać o tym jak się robi "wyszukiwarkę". Ogólnie do małych serwisów jeszcze LIKE przejdzie - przy większej ilości danych radzę zapoznać się z wyszukiwaniem pełnotekstowym (przynajmniej indeksy fulltext i match against na początek). W pokazanym przez Ciebie przykładzie szukasz po całej szukanej frazie co może być słuszne albo i nie w zależności od założenia.
Opcje są ogólnie 3:
1. Pełna fraza
Ktoś wpisze "Warszawa Kraków" - zostaną zwrócone te wpisy, które mają dokładnie taki zapis
2. Wszystkie słowa z frazy naraz ale traktowane oddzielnie:
Musisz podzielić frazę na wyrazy (po spacji - np. funckja
explode), usunąc spację z końca i początku każdego słowa i utworzyć zapytanie typu:
SELECT ... FROM ... WHERE pole LIKE '%slowo1%' AND pole LIKE '%slowo2%' AND pole LIKE ... -- itd
3. Przynajmniej jedno ze słów z frazy
Tak jak wyżej tylko zamiast AND dajesz OR:
SELECT ... FROM ... WHERE pole LIKE '%slowo1%' OR pole LIKE '%slowo2%' OR pole LIKE ... -- itd
Ogólnie to wszystko. W przypadku jednak gdy szukasz po kilku polach musisz taką operację wykonać dla każdego - czyli dynamicznie tworzyć zapytanka.