Hola, no se como estas realizando la paginación pero no es dificil resolver este problema. Como no tenemos a mano el código que usas no se puede detectar cual puede ser el error.
Yo sugeriria algo así:
Código PHP:
for ($i=1;$i<$totalregistros;$i++){
echo "<a href=index.php?palabra=provincia&pagina=".$i.">".$i."</a>";
}
Igual revise las comillas por si de pronto las puse mal.
Como se puede ver al imprimir así los enlaces siempre va a estar la condición de que pagina sea igual a provincia(el cual me imagino es un dato dinamico y no estatico así que podria colocarse como $provincia y de pronto venga de algun formulario)
Lo de pagina significa la cantidad total de registros que salen de la consulta, entonces a medida que se hace la consulta se va recorriendo.
Para poner un ejemplo digamos que se tiene 50 registros y se quieren mostrar de 10 en 10, entonces significa que tendremos en total 50/10=5 paginas el cual seria el valor de $totalregistros;
Por ultimo es bueno aclarar que la consulta debe estar limitada para que recorra los registros por ejemplo del 1 al 10 del 11 al 20 del 21 al 30 etc entonces cuando se coloque el limit a la consulta debe estar en función del valor de pagina para que así pagina 1 corresponda con un limit de 1 a 10, pagina 2 del 11 al 20 etc.