There's no one hard answer. It depends on the structure of the site. Put yourself in the shoes of a typical user -- would they likely want to jump all over the place to accomplish different tasks, or are they likely to want to move only up and down the directory tree? A compromise would be "up" links to major section header pages, and sideways links to all close sibling pages. What you don't want is so many links that it becomes difficult to figure out which one to use. No one will want to spend several minutes studying a list of hundreds of links, in order to decide which one to click on. Of course, you always want to be able to go Home, and you never want an active link to the page you're on (it's confusing to click on the link and nothing appears to happen). If you have more than a dozen or so pages, I wouldn't try to directly link to all of them from each page. Choose a structure that will allow you to get anyplace with no more than a "few" clicks of the mouse ("few" depending on how many pages there are -- maybe log base 10 of the page count would be a good objective).

In the web design classes I've taken, I've always been told that the same menu should be on every page, with links to every page. The idea is that people should be able to go quickly and easily from any page to any page, and that they will always find the menu in the same place on every page. If a site I'm designing has a lot of pages, I create 6-7 main menu items, with pop-up sub-menus where needed. I just make the menu part of the template that I use for every page. That means that there will be a link to the page you're on -- for instance, a link to the home page from the home page -- but that's not a big deal.