your checkboxes should be an array and the value of each should be the id of the record you want to delete in the database.
<input type="checkbox" name="var[]" value="4"><br>
<input type="checkbox" name="var[]" value="8"><br>
<input type="checkbox" name="var[]" value="13"><br>
then, to delete all the checked records
$query = mysql_query("DELETE FROM your_table WHERE id IN ('" . implode("','", $_POST['var']) . "')") or die(mysql_error());
I'd backup your data before doing anything. Just a good precaution.
Cgraz