Hola,
El problema que tienes es que la variable que propagas por la URL es criterio y esta variable no la recoges en ningun sitio. Ademas, tal como tienes planteado tu script, no deberias pasar criterio, sino apellidos y demas variables que uses para crear $criterio en el script. Asi que en tu caso el link seria:
Código PHP:
echo "<a href='busqueda.php?pagina=" . $i . "&apellidos=" . $apellidos . "&dni=".$dni."'>" . $i . "</a> ";
por ejemplo (suponiendo que guardes en $apellidos el valor del GET o del POST segun corresponda).
Aparte de eso, la forma en que insertas los arrays $_GET y $_POST en una cadena es incorrecta. Deberia ser:
Código PHP:
$criterio.=" and APELLIDO like '{$_POST["apellidos"]}'";
o concatenandolo con el punto.
Suerte.