Относительные ссылки и использование include

к инклюдам этот вопрос не имеет никакого отношения.

В файле навигации прописаны относительные ссылки к страничкам.

Это неправильно. Ссылки должны быть абсолютные:

для того, чтобы любая ссылка гарантированно работала, независимо от того, из какого места сайта она вызывается, она должна быть абсолютной.

Если у вас на сайте есть, допустим, два раздела:
http://www.example.com/about/info.php
и
http://www.example.com/job/vacancy.php

то, если в файле info.php сделать ссылку просто на vacancy.php, то браузер ее не найдет - он будет искать адрес http://www.example.com/about/vacancy.php, достраивая путь от текущего каталога.

Поэтому надо писать полный путь от корня сайта - /job/vacancy.php
Всё это касается, естественно, не только тегов но и и любых других, где используются ссылки на другие файлы.

Ссылки на локальные адреса следует писать без указания протокола и домена - только путь от корня сайта - /job/vacancy.php. Ссылки же на другие сайты следует писать полностью - http://www.example.com/job/vacancy.php.

чтоб вернуться на уровень выше пишите ../. Если нужно с папки обратится в соседнюю папку тогда сначала выходим с текущей папки и заходим в нужную:

../folder/file.php

Возможно вам лучше будет использовать абсолютный путь..

"http://" . $_SERVER['SERVER_NAME'].. и сюда уже прописывать в ссылках остальной путь. Н-д :

"http://" . $_SERVER['SERVER_NAME'] . "/folder/header.php".

Тогда независимо откуда вы обращаетесь к файлу ссылка не меняется - не взникает путаницы

Лучше использовать структуру MVC, может будет не настолько удобно как в твоем случае но правильнее и не будет путаницы