Som MartinK säger, om din tabell bara har några hundra rader bör din fråga vara ganska snabb även utan optimering - det är värt att kolla vad som händer.
Det bästa sättet att söka i textfält är dock att använda fulltextindexering (http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html) - detta är designat för just det fall du åter beskriver.