Cuando pinchas en un link, se carga el script desde cero. Desaparecen todos los valores de $_POST, solo tendras los $_GET que esten en el link que han pinchado. Como $_POST esta vacio, tus consultas no devuelven registros y por eso no se muestra nada.
Asi que no te queda otra que pasar todos los valores que recibes por POST y añadirlos en los enlaces de la paginacion. Y en la carga de las paginas de paginacion tampoco estaran en POST, sino en GET, asi que podrias usar $_REQUEST para no tener que estar haciendo la diferencia.
Asi que tus links de paginacion quedaran
echo "<a href='$PHP_SELF?pg=".$i."&palabra=".$_REQUEST['palabra']."'>".$i."</a> ";