Nel form html tutti gli input checkbox devono avere come avere attributo "name" un nome seguito da parentesi quadra aperta e chiusa.Così per es.
codice:
 <input type="checkbox" name="record[]" value="1">
Poi una volta inviato il form alla pag elimina_record.php per avere i record selezionati fai così:
Codice PHP:
$checked $_POST["record"];
foreach(
$checked as $value)
    {
    
//Supponendo che i valori del checkbox fossero gli ID della tabella 
    
$query=mysql_query("DELETE FROM table WHERE id=$value");
    } 
Ciao