Ciao
l'elemento che vorresti rendere "flottante" a sx, lo devi rendere "float:left"

Al contrario, per l'elemento che vuoi a destra: float:right.

Quindi, se ho capito bene, avrai:

#menu{
width: 120px;
border:1px solid red;
padding:20px;
margin:25px;
float:left;
}

#intestazione{
width: 660px;
border:1px solid blue;
padding:20px;
margin:20px;
float:right;
}

Il box contenitore dei due elementi "flottanti" lo devi rendere "overflow:hidden"

Al di sotto dei 2 elementi, se devi metterne altri, prima di questi inserisci un elemento vuoto, che "pulisca" il tutto.

per es.

<div style="clear:both;"></div>

Non ho replicato la tua pagina su un file in locale, spero non ci sia nessuna incongriuenza.

Saluti