Pages that you create and publish will show up on the custom menu page in the "pages" module (sometimes you have to click the "view all" link to see all of them). You add pages from there.
If you want an external link, then you use the "custom link" module on the custom menu page and the add that link to the menu.
You can add categories, pages and even specific posts if you wish.
After adding the pages, and/or categories and/or custom links to the menu and arranging them in the order you want them, save the menu. The go to the Theme location module on the custom menu page and select your custom menu for the "primary" location.
It's all there in the link that you referenced.