Una forma de hacerlo seria dandole a la propiedad value de cada checkbox el id del registro que representa:
Código PHP:
<?
$resultado = mysql_query("SELECT id ....");
while ($fila = mysql_fetch_array(resultado)) {
....
$id = $fila['id'];
echo "<input type=\"checkbox\" name=\"tu_nombre[]\" value=\"$id\">";
....
}
?>
Y en la página donde envias el formulario:
Código PHP:
<?
foreach ($_POST['tu_nombre'] as $valor) {
$consulta = "DELETE FROM tu_tabla WHERE id = $valor";
mysql_query($consulta);
}
?>
Saludos.