Usando javascript+ajax le cose si semplificano molto... ti ho fatto velocemente un esempio (mooooolto migliorabile), dal quale puoi comunque trarre qualche spunto:

paginazione.php

Codice PHP:
<?php

    session_start();
    
    if (!isset($_SESSION['checkbox']))
    {
        $_SESSION['checkbox'] = array();
    }

?>

<script src="//ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.min.js" type="text/javascript"></script>

<script>

$(document).ready(function() 
{
    $('.cb').click (function ()
    {
        var checkbox = $(this);
        var status   = '';
        
        if (checkbox.is(':checked'))
        {
            status = 'seleziona';
        }
        else
        {
            status = 'deseleziona';
        }

        $.ajax({
                       // in questa chiamata c'è il minimo indispensabile
            url: 'elabora_checkbox.php?id=' + checkbox.attr('id') + '&status=' + status
        });
    });
});
</script>

<?php
 
    $checkboxes = array('cb_01', 'cb_02', 'cb_03', 'cb_04', 'cb_05');
    $input      = '';
    
    foreach ($checkboxes as $id)
    {
        if (isset($_SESSION['checkbox'][$id]))
        {
            $input .= "<input id=\"$id\" class=\"cb\" type=\"checkbox\" name=\"nome\" value=\"valore_5\" checked>";
        }
        else 
        {
            $input .= "<input id=\"$id\" class=\"cb\" type=\"checkbox\" name=\"nome\" value=\"valore_5\">";
        }
    }
    
    echo $input;
?>
elabora_checkbox.php

Codice PHP:
<?php

    session_start();
    
    if (!isset($_SESSION['checkbox']))
    {
        $_SESSION['checkbox'] = array();
    }
    
    if (isset($_GET['id']) && isset($_GET['status']))
    {        
        $id     = $_GET['id'];
        $status = $_GET['status'];
        
        if ($status == 'deseleziona')
        {
            unset($_SESSION['checkbox'][$id]);
        }
        elseif ($status == 'seleziona')
        {
            $_SESSION['checkbox'][$id] = true;
        }
        else 
        {
            // non conosco lo status, gestisci
        }
        
    }
    else 
    {
        // non ci sono id e status in GET, gestisci
    }