Si usas un paginador casi seguro que tenga para propagar variables. El problema que supongo que tus checkbox están en un form, entonces la primera vez que busca lo hace bien.
Pero como el paginador es un enlace, propaga por url método get, por lo cual tendrás que pasarle tu los datos, con algún método de propagación.
De todos modos te dejo un paginador
Saludos