Checkbox + Session

Olá amigos!

Boa noite!

Estou com uma dúvida tremenda, se alguém puder me ajudar, pois já matutei bastante sobre o assunto e nao consegui resolve-lo

Tenho uma paginacao de resultados do tipo Google.

Logo, sao exibidos 100 registros e os demais ficam nas paginas 1 2 3 4 5...

Na frente de cada registro, tenho um checkbox, que traz consigo o id do registro.

Ocorre que o usuario pode selecionar 20 checkbox na primeira pagina, mas quando vai para a segunda, os valores marcados na primeira nao sao somados aos da segunda, ou seja, nao sao gravados aqueles valores cujo o user ja havia marcado.

Gostaria de, ao menos, inserir os valores do id na sessao assim que o usuário clicasse nele, pois daí nao daria refresh.

Enfim, nao sei se isso é possivel com PHP?

Li a respeito no forum e a maioria faz com JS ou AJAX, mas nao o consegui fazer....

Help-me, please!!

Abs

Ronaldo