Allora....
Il name della checkbox lo devi segnare come fosse un array e devi aggiungere un valore, solitamente si usa quello dell'ID di ogni record. Per cui:
codice:
<input type=\"checkbox\" name=\"checkbox[]\" id=\"checkbox[]\" value=$id />
Questo significa che, qualora venissero segnate due o più voci, la variabile $_POST['checkbox'] conterrà un array le cui voci corrispondono al numero corrispondente ad ognuno dei value selezionati.

Fin qui ci sei??
Bene, ora lo script che riceve i valori sarà del tipo:
Codice PHP:
$valori_da_cancellare $_POST['checkbox'];
// creo una stringa con tutti i parametri separati da una virgola
$val implode(","$valori_da_cancellare);

// la stringa SQL sarà quindi
$sql "DELETE FROM tabella WHERE id IN ($val);