Como los checkboxes que imprimes son parte de un ciclo, tus checkboxes deben tener un nombre de la siguiente forma:
Código HTML:
<input type="checkbox" name="nombre[]" value="elvalor" />
De esta manera estarás creando un arreglo de checkboxes; ahora cuando presiones el botón eliminar debes enviar todos los checkboxes por post y en tu php hacer mas o menos esto:
Código PHP:
foreach($_POST['nombre'] as $item)
{
//Aqui iria la consulta para eliminar el registro correspondiente
}
Es importante considerar que a tu archivo eliminar.php unicamente llegarán los valores de los checkboxes que estén seleccionados.
Espero esto te sirva.