Ciao,
riguardo il primo punto, non ho capito se mediante quell'input vuoi semplicemente far sì che vengano mostrate solo le riche della tabella pertinenti (in tal caso si può fare anche con javascript) oppure vuoi mostrare delle informazioni aggiuntive; nel secondo caso, consiglio comunque un caricamento asincrono con ayax che richiami un file php contenente le opportune query, oppure se non conosci ayax puoi semplicemente non mettere niente nella action del form che contiene l'input (action="") in modo che i dati vengano inviati alla stessa pagina della tabella, e inserisci le query prima del punto dove intendi visualizzare le informazioni.
riguardo i contatori di pagina, prima di tutto esegui la query di ricerca, che ti restituisce una sorta di "tabella" con tutti i record trovati. a questo punto conti il numero di righe (se il db è mysql usi mysql_num_rows($risultato query)) e con un semplice algoritmo stampi i numerini delle pagine, evidenziando il primo.
A ogni numerino farai corrispondere un link alla stessa pagina, ma aggiungerai una query string che indichi la pagina di risultati da caricare; a questo punto stampi i risultati desiderati con un ciclo che esegua n volte la funzione mysql_result($risultato query, $numero_riga, $numero_colonna) (lascio a te i dettagli).
In realtà si può fare anche in altri modi (ad esempio combinando mysql_data_seek($numero_riga) con mysql_fetch_assoc($risultato query)), ma questo mi è sembrato il più facile da capire.