Lo puedes poner en cualquier parte, pero siempre antes de usarlo, con lo que al principio del archivo será el mejor sitio. En mi caso, tengo las variables dedfinidas en un archivo llamado config.inc.php, al cual llamo manualmente desde cada archivo PHP que creo, pero a partir de ahí todas las llamadas son siempre igual:
<?
require_once("comun/__config.inc.php");
require_once($config["BASE_PATH"]."comun/__conecta.inc.php");
require_once($config["BASE_PATH"]."comun/__cookies.inc.php");
[mas abajo]
include $config["BASE_PATH"]."comun/__cabecera.inc.php";
include $config["BASE_PATH"]."comun/__banner_top.inc.php";
[...]
?>
En este caso puedes observar que primero llamo a la configuración, luego activo la conexión a la BBDD (no siempre es necesária), luego hago una gestión de cookies.
El archivo de configuración define las rutas ( $config["BASE_URL"] para los enlaces y $config["BASE_PATH"] para los includes PHP).
Mas adelante, cargo la cabecera de la web, que incluye el menú de login, el logo de la web y el menú de navegación.
Finalmente cargo el banner superior de la web.
Copiando esta estructura y cambiando el 1er include funciona en cualquier carpeta.
EDIT:
Por lo que veo, en tu caso quieres las URL. Entonces, la solución quedaría:
menu.inc.php:
<?
$config["BASE_URL"] = "http://www.naguissa.com";
?>
<a href="<?= $config["BASE_URL"] ?>/dir1/pag1.php">Enlace 1</a><br />
<a href="<?= $config["BASE_URL"] ?>/dir2/pag2.php">Enlace 2</a><br />
<a href="<?= $config["BASE_URL"] ?>/dir3/pag3.php">Enlace 3</a><br />
Ahora, cuando lo necesitases bastaría hacer:
<? include( "../../menu.inc.php"); ?>
en cualquier archivo PHP, cambiando el "../../" por la ruta necesaria para hacerlo funcionar.