Es mas un tema de Javascript que de PHP. Yo hago lo mismo que David el Grande propuso con su 2do ejemplo, solo que usando jQuery.
Código javascript
:
Ver original$('#pg2').click(function() {
//accion
return false;
});
Y creo los links para la paginacion usando PHP.
<a href="talcosa.php?page=2" id="pg2">Pagina 2</a>
Asi si Javascript esta desactivado, la pagina se recarga enviando el parametro de la pagina la cual quieres ver.