This is one of the trivial patterns in the pattern language: Add SiteNavigation to your site. Some people seem to think that a wiki is just a directed graph with links pointing to pages, and there is no inherent structure, therefore providing structure and thus meaningful navigation is impossible.
Newcomers don't know what is available. They can follow links, but that alone will now allow them to build a cognitive map of the site's content. The site must also provide means for visitors to locate themselves on this map.
At the same time, don't overwhelm visitors: If your pages are short, don't add big sidebars with lots of information, lest visitors be distracted visually from the page content.
Use a front page that is easy to reach for the general overview of the site. What are the choices available to visitors? Keep the number of choices small. Add enough information to allow meaningful choice.
One particular implementation would be to list all category pages on a wiki on the front page, and every category page lists all the pages in the category. All links have a small one or two sentence comment with extra information. See ForwardIndex and WikiCategories.
You may also want to use two-dimensional map instead of a one-dimensional lists. Eventhough lists can be hierarchical instead of flat, lists limit your ability to indicate related topics. Don't use a three-dimensional space unless you feel that there are no usability issues. There usually are.
Within a page, do not use more than 10% of the screen for navigation links. If the page content is small, use smaller navigation aids.
When offering information about changes in time, a one-dimensional representation is the only thing that makes sense. This is why RecentChanges is a list. It may make sense to use a hierarchical list or filtering, however, to improve usability.
Provide a link to help pages.
If you have an area for "news", provide a link to get an overview of what happened (eg. RecentChanges or a blog), and provide a link to the place where you can register such news items. Do this for similar repetitive tasks.
Since visitors following deep links must find help, make navigational help available from every single page. Do not use separate frames for navigational purposes.