Any time a change is made to the navigation, such as adding a new page, the entire site needs to be published. Right-click on the folder at the top of your file structure (it should be your site name) and click publish.
It is also important to make sure that the option for "Include in Navigation" is set to "Yes" on your new page.
You may also need to publish your entire site if you make these changes that affect the navigation:
- Reorder a page
- Change the name of a page
- Delete a page from your site
- Have a web administrator move a page to a new folder