Hola:
Si tienen el mismo name, la respuesta es casi tribial:
<form ...>
<input type="checkbox" onchange="selecciona(this, 'ciudad') />
<input type="checkbox" name="ciudad" value="Madrid" />
<input type="checkbox" name="ciudad" value="Barcelona" />
<input type="checkbox" name="ciudad" value="Torremolinos" />
</form>
Y el script:
function selecciona(yo, campo) {
for (i = 0, f = yo.form, c = f[campo], total = f[c].length; i < total; i ++)
c[i].checked = yo.checked;
}
Lo puse "a capella" así que puede tener algún error, pero intenta interpretarlo... Y para más info, te paso un tuto:
El abc de los formularios
Saludos