Yo empezaría DataTables:
https://datatables.net
Simplemente generas tu tabla en HTML de forma normal... y a continuación con Jquery, en el onReady inicializas la dataTable.
Automáticamente se te paginara, te añadirá un buscador, etc...
Después ya puedes jugar en el inicializador con el numero de registros por página, opciones de exportacion, ordenación, etc...