Allora...per prima cosa, hai detto che ENTRAMBE le colonne (contenuti e navigazione) sono posizionate in modo assoluto? Perché non è il massimo...il footer per es. come hai fatto a posizionarlo sotto queste colonne? I posizionamenti assoluti estraggono i box dal flusso del documento e quindi questi box non influenzano il layout degli altri box (che sono posizionati in modo statico). Ti consiglio quindi 2 "soluzioni" possibili:

1. Se sai con esattezza quale delle 2 colonne è SEMPRE la più alta, posizionala normalmente (in modo statico) e assegnale un margine pari alla larghezza dell'altra colonna sul lato corripondente. L'altra colonna può rimanere posizionata in modo assoluto.

2. Invece che position: absolute, usa float: left o float: right su entrambe le colonne.

In entrambi i casi, hai bisogno di un box "contenitore" per le 2 colonne (puoi usare anche l'eventuale "container" della pagina). A questo box, di cui non specifichi l'altezza, devi applicare un'immagine di sfondo ripetuta verticalmente (alta anche solo 1px) che crei l'"illusione" di essere lo sfondo della prima colonna.

Se usi la seconda soluzione però, devi ripristinare il flusso del documento subito prima di chiudere il box contenitore delle due colonne (o, se il box footer è interno a questo, puoi usare lui stesso per farlo). Nel primo caso hai bisogno di un elemento
appena prima della chiusura del contenitore a cui applichi una classe (chiamala clear ad es.) fatta così:

codice:
.clear {
clear: left; /* se le colonne sono entrambe float: left */
clear: right; /* se le colonne sono entrambe float: right */
}
Nel caso usassi il footer per "ripulire" il float, basta che nella sua regola di stile aggiungi la dichiarazione clear: left o clear: right, come spiegato nel codice precedente.

Per le immagini...non vedo che problemi ci sono. Basta che le applichi come sfondo ai vari box che ti interessano. Ovviamente bisogna che i box in questione abbiano dimensioni definite.