Para implementar lo que estamos comentando lo primero que debemos hacer es conectar con la base de datos que vamos a tratar.

Realizamos la consulta:

$consulta_noticias = "SELECT * FROM noticias";
$rs_noticias = mysql_query($consulta_noticias, $con);
$num_total_registros = mysql_num_rows($rs_noticias);

En el ejemplo queremos paginar todas las noticias publicadas de un sitio Web. En la tercera línea estamos obteniendo el número total de registros para más adelante saber cuantas páginas se van a necesitar.

Si esta consulta tiene registros, procedemos a montar todo lo necesario para realizar la paginación:

//Limito la busqueda
$TAMANO_PAGINA = 10;

//examino la página a mostrar y el inicio del registro a mostrar
$pagina = $_GET["pagina"];
if (!$pagina) {
   $inicio = 0;
   $pagina = 1;
}
else {
   $inicio = ($pagina - 1) * $TAMANO_PAGINA;
}
//calculo el total de páginas
$total_paginas = ceil($num_total_registros / $TAMANO_PAGINA);

Utilizamos la variable $TAMANO_PAGINA para guardar el límite de la búsqueda, es decir, la cantidad de registros a mostrar en cada página. Lo que sigue estamos capturando la página en la que estamos para mostrar los registros que toquen.

A continuación, ejecutaríamos la query que variará en cada página, por ejemplo:

$consulta = "SELECT idNoticia, titulo FROM noticias ORDER BY fecha_insercion DESC LIMIT ".$inicio."," . $TAMANO_PAGINA;
$rs = mysql_query($consulta, $con);
while ($row = mysql_fetch_array($rs)) {
   //Aqui mostrariamos los datos que se quieran sobre la noticia
}

Si nos fijamos en la query anterior vemos que queremos mostrar las noticias ordenadas por fecha de publicación limitando la busqueda de la página en la que estemos hasta el tamaño de la página que marcamos inicialmente con 10 registros.

Después solo queda mostrar la paginación:

if ($total_paginas > 1) {
   if ($pagina != 1)
      echo '';
      for ($i=1;$i<=$total_paginas;$i++) {
         if ($pagina == $i)
            //si muestro el índice de la página actual, no coloco enlace
            echo $pagina;
         else
            //si el índice no corresponde con la página mostrada actualmente,
            //coloco el enlace para ir a esa página
            echo '  '.$i.'  ';
      }
      if ($pagina != $total_paginas)
         echo '';
}