Se non ricordo male in Java i packages indicano anche un percorso. Se è così i namespace C++ non hanno niente a che fare con questo. Un header files può contenere diversi namespace al suo interno, namespace annidati, namespace anonimi etc.
http://www.cplusplus.com/doc/tutorial/namespaces/

Se tu crei una tua libreria e la metti un namespace è corretto, ma non sei obbligato a dividere i vari file in cartelle.

Presumo che l'organizzazione che hai mostrato sia dovuta alla natura Java-oriented di Eclipse (che di per se non è sbagliata: solo un po' complicata da gestire, forse).

Quindi per far sapere al compilatore dove sono gli header, basta che glielo indico nelle proprietà del progetto (in eclipse, ad esempio)?
Si. In genere si indica la cartella padre di quella dove sono posti gli header file, poi puoi usare le parentesi < > per includere gli header che interessano. Devi però aggiungere anche i file .cpp al progetto altrimenti il linker protesta.