For the new page to appear in all the relevant menus, you need to select "Publish" for each page that has a menu where the new page will be displayed. This ensures that the menus on all pages are updated to include links to the the newly published page.
Also note that only pages included in the site tree are visible when published. To include or exclude a page from the menus you need to edit the properties of a page. To do this select "Page Properties" from the "Edit" menu; make sure the "include in menus" option is not selected and then click the "save changes" button. Now Publish all the other pages that link to this page to remove the links from their menus.