Como diz o MartinK, se sua tabela tiver apenas algumas centenas de linhas, sua consulta deve ser bem rápida mesmo sem otimização - vale a pena verificar o que está acontecendo.

No entanto, a melhor maneira de pesquisar campos de texto é usar a indexação de texto completo (http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html) - isso é projetado exatamente para o caso em que você re descrevendo.