Hola,
Posiblemente, fetchNavegacion genera los vínculos a las siguientes páginas, pero ... ¿Qué sabe PHPPaging sobre esas variables del POST?
Cita:
Iniciado por Pike 
$pais=$_POST['pais'];
$searchtype=$_POST['searchtype'];
$searchterm=trim($_POST['searchterm']);
$links = $paging->fetchNavegacion();
echo $links;
Seguramente los vínculos que genera son 'pagina.php?pagina=X', y cuando presionas ese vínculo no lleva los parámetros del post original (osea la primera vez que llegó a esa página).
http://phppaging.phperu.net/ejemplos.php?tipo=post
Saludos,