You could include it relative to the current directory, like so:
require_once(dirname(__FILE__) . '/template.php');
dirname(FILE) will translate to the directory of the current script (index.php) and the line above will append '/template.php' resulting in the full path to the template.php side-by-side to the index.php file.
I find it best to include files this way vs without a full path to avoid issues with the PHP search path, for example. It's very explicit this way.
UPDATE: I misunderstood the original question. It sounds like template.php isn't copied, only index.php is. So you'll have something that could be like:
template/template.php
template/index.php (just a template)
foo/bar/index.php
foo/bar2/index.php
Since people can hit the foo/bar/index.php for example without funneling through a central script, you'll have to somehow find the template no matter where you are.
You can do this by setting the PHP include_path, for example through a .htaccess on a Apache server:
php_value include_path ".:/home/<snip>/template"
Then in each index.php you can include template.php and it'll search the current directory first, then try your template directory.
You could also compute the relative path when copying the script and put an include in there with the proper number of '..' to get out (e.g. '../../template/template.php'). It's kinda fragile, though.