E meno male che ti ho detto che le funzioni mysql_ sono state abbandonate e di usare almeno mysqli_
Te lo riconsiglio, perché appena il tuo script si troverà a girare su una versione recente di PHP non funzionerà più e dovrai riscriverlo, quindi meglio partire subito con una versione che non abbia questo problema, no?

Comunque, per la ricerca, fai un form con un campo text, l'utente scrive una parola e invia, lo script indicato nell'action riceve il dato, lo usa per generare la stringa da usare come query.