Si potrebbe realizzare il tutto in un'unica pagina (elimina.php). Ti posto un codice d'esempio (segui i commenti!)
Codice PHP:
[FONT=courier new]<?php
/*
* controllo se i dati sono stati inviati dal form
* se è stato selezionato almeno un checkbox
* scorro l'array $_POST contenente l'id selezionato dal checkbox
* lancio la query DELETE ed elimino l'id selezionato/i
* ($db contiene mysql_connect)
*/

if(isset($_POST['submit'])) {
  if(!empty($_POST['id'])) {
    foreach($_POST['id'] as $value) {
      mysql_query("DELETE FROM tabella WHERE id = '$value'", $db);
    }
    echo "msg di conferma";
  }
  else { 
  echo "Seleziona almeno un Record";
  }

/*
* se il form non è stato inviato, stampo tutti i record da eliminare
* seleziono tutti i record dalla tabella
* conto quante righe ci sono nella tabella
* se c'è almeno 1 record stampo il risultato
* setto gli attributi "value" e "name" del checkbox per gestire l'id come array
* se non ci sono record nella tabella
* stampo un msg per comunicare che non c'è nulla da eliminare
*/

} else {
$result = mysql_query("SELECT * FROM tabella", $db);
$count = mysql_num_rows($result);
if($count) {
  echo '<form action="elimina.php" method="post">';
    while($records = mysql_fetch_array($result)) {
      echo '<input type="checkbox" value="'.$records['id'].'" name="id[]">';
      echo $records['tuo_campo_descrizione'];
    }
      echo '<input type="submit" name="submit" value="Elimina"></form>';
  } else {
    echo "Nessun record da eliminare.";
  }
}
?>[/FONT]
Ovvio che il campo id è inteso come primary key e auto increment. Può essere certamente migliorato, ma per iniziare dovrebbe andar bene. Adattalo ai tuoi valori (nomi tabella e campi), non è complicato...