Bueno, no veo como envías la información, pero asumiendo que será por POST, y asumiendo que sabes como hacer un insert del registro normal, en tu script donde recibas la información:
Código PHP:
Ver originalmysql_query("insert into mi_tabla values ('$valor1','$valor2','$valor3','$etc')");
foreach($_POST['IDDESTINOSSUGERIDOS'] as $n =>$valor){//recorremos las opciones del select seleccionadas
mysql_query("insert into mitabla2 values ('$ultimoid','$valor')");//insertamos id relacionado y valor del select }