Pues teniendo el total de páginas ($total_pag) me parece algo de lo más trivial:
Código PHP:
$pagina_anterior = $pagina - 1;
$pagina_siguiente = $pagina + 1;
Obviamente, habría que añadir todas las comprobaciones de si se trata de la primera página, de la última, etc.
Un saludo