James, one way to do this is with array_unshift function.
Everytime you choose a checkbox, add a Javascript onClick event handler to use a PHP array_unshift. I had this same issue and solved it like that.
Or, another way is to have your primary key in a hidden form variable and when they form is submitted, have while go through the pimary keys and inside the while loop, do an IF loop to check if the checkbox is "on" (case sensitive). If the checkbox is on, run an SQL DELETE command, execute the query, and let the loop go to the next item