Beh, la query sql da me proposta era un banale esempio.

Detto questo sapendo quante righe (mysql_num_rows) di risultati si hanno puoi trarre delle conclusioni, se poi il numero di mysql_num_rows è maggiore di un numero da te preimpostato splitti i risultati su varie pagine.

Passando ad esempio come parametri get il termine ricercato e la pagina, poi da pagina due non partirà dal record 0 ma dal record 25 (Esempio nel caso te voglia mostrare 25 record a pagina).

La query sql poi la gestisci te... però in teoria potrebbe bastarti sapere il numero di risultati.