Trick your users -- have all your page links (next, prev, "go to page..") submit the form instead of perform a simple redirect. All checked items should be stored into a session. That way, when a user goes BACK to a page that has previously checked items, they can choose to UNcheck them as well.
The only problem here is that you have to be a little clever to figure out if a user has unchecked an item. You need to know all of the items that were displayed on that page, which of those items are already checked in the session, and which items are checked in the submitted form.