Beh la soluzione e' sempre il limit x,y .
Io farei una cosa del genere :
Codice PHP:
$currPage = abs($_GET["page"]);
$counts = 20 ; //Righe per pagina
$pageFrom = ($counts*$currPage) :
$pageto = $pageFrom+$counts ;
// Incrementiamo di 1 se nn siamo sulla prima pagina per evitare la ripetizione
//dell'ultimo ris della pag prec
if( $pageFrom!=0)
$pageFrom++;
$q = "select * from users order by nome asc limit ".$pageFrom.",".$pageTo." " ;
etc.....