Hola
Bueno, tu los tienes como hipervinculos que viajan a la pagina eliminar, pero un check por si solo no te va a viajar, entonces tienes que ponerle en el evento onclick por ej submit() y tendrias que manejar todo en un form que apunte a la pagina eliminar.php o no ponerle el submit en el onclick y crear un boton que sea un submit, en fin, al gusto de cada cual.
Código PHP:
<form action="eliminar.php">
<TABLE BORDER=1 CELLSPACING=1 CELLPADDING=1>
<TR><TD> <B>Nombre</B></TD> <TD> <B>Apellidos</B> </TD> <TD> <B>Borrar</B> </TD></TR>
<?php
while($row = mysql_fetch_array($result)) {
printf("<tr><td> %s</td><td> %s </td>
<td><input type=checkbox name=id_clientes value=%d onclick=submit()></td>
</tr>", $row["nombre"],$row["direccion"],$row["id_clientes"]);
}
?>
</FORM>
Espero te sirva, suerte.