$max_res       = 15;
$from          = (($page * $max_res) - $max_res);


$abfrage       = $n_eintraege = mysql_query("SELECT * FROM `TABELLE` LIMIT $from, $max_res");


$total_results = mysql_result(mysql_query("SELECT COUNT(*) as Num FROM `TABELLE`"),0);
$total_pages   = ceil($total_results / $max_res);


if($page >= 1){
 $prev        = ($page - 1);
 $script     .= "<a href=\"".$_SERVER['PHP_SELF']."?page=$prev\">&lt;&lt; Zurück</a>&nbsp; ";
}

for($i = 1; $i <= $total_pages; $i++){
 if(($page) == $i){
   $script   .= "&nbsp;[ <font color=\"#CC0000\"><b>$i</b></font> ]&nbsp; ";
 } else {
   $script .="<a href=\"".$_SERVER['PHP_SELF']."?page=$i\">$i</a> ";
 }
}

if($page < $total_pages){
 $next      = ($page + 1);
 $script   .= "&nbsp;<a href=\"".$_SERVER['PHP_SELF']."?page=$next\">Nächste &gt;&gt;</a>";
}

Ich mach das normalerweise so, dass ich z.B. max 11 Seiten anzeige, auch wenn es mehr gibt
Am anfang also 1, 2, 3....11

Je nachdem wie weit der User blättert zeige ich die aktuelle (fett) plus die 5 davor und die 5 danach.

Also z.B. 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15

Dann am besten noch zwei Links für die erst und letzte und evtl. noch 2 Links für vorherige 10 und nächste 10, dann hast Du so ziemlich alle Bedürfnisse abgedeckt