Go see the xml layout files : app/design/frontend/<your_package>/<your_theme>/layout/catalog.xml and page.xml
if you don’t have a special package nor a special theme, replace both of these by “default”.
You’ll have different tags to mess with in the XML file. The <default> tag allows to put a general block that will appear in all sub-pages. That’s generally where you’ll find the navigation menu and header.
you also have the other tags, like, <module_controller_default> and <module_controller_action>. These are the handles that will get triggered if the corresponding page is called.
PM me for more.