Bueno, principalmente, depende de la versión de MySql que tengas...
Pero igualmente lo que tienes que hacer, es calcular la cantidad de registros devueltos por la consulta, luego calcular cada cuantos quieres mostrar (total/cada) con lo cual obtienes la cantidad de 'paginas'.
Con estos datos, armas la consulta con un limit al final.. donde el primer valor será el número de página multiplicado por la cantidad de mensajes a mostrar, y el segundo cada cuantos se muestra:
SELECT ..... LIMIT 0,10 ( pagina 0, de 0a 10 )
SELECT ..... LIMIT 10,10 ( pagina 1, de 10 a 20 )
SELECT ..... LIMIT 20,10 ( pagina 2, de 20 a 30 )
Espero te halla servido.
Altareum.