Hola:
Lo que quieres es algo trabajoso, las paginaciones que he hecho no son con tablas, pero tal vez te sirva este ejemplo:
Ajax: Galería de imágenes paginada, donde puedes ver el código javascript en la última pestaña... la parte php creo que no te supondrá mucha dificultad.
Saludos
