You would not be able to do this with standard pagination since storing the checkboxes is a form thing and needs to be posted to be remembered.
Perhaps you could do an ajax call with each checkbox click and store (or clear) it in the user's session.
Suppose you have 30 items (e.g. with id's) across 3 pages. You could have 3x ajax request for items 3,4 and 7 (store these in session) then the user paginates to page 2, and clicks on the 5th row which is item 15. Now you have 3,4,7,and 15 in session. They then click on the next page and select item 22 (now 3,4,7 and 22 'checked' in session). Finally they press submit, and in your controller you grab all the IDs from session.
A refinement would be to pass the array from session back into the view each time so that you can check boxes for the user if say they go back to page 1 and expect to see 3,4 and 7 still selected.