Stef has 2 great video tutorials explaining exactly this over on www.idea22.com: PHP Includes Part 1 and PHP Includes Part 2
Not sure if this is in the videos - but it's generally a good idea, especially if the site is set up with sub-folders, to use the absolute paths pointing to the include files, and for anything the include itself points to - that can save a lot of wondering why something suddenly isn't showing up...