make the link first (see examples when you click “Edit this page”, above or when you edit your sidebar)
save your changes
click the link (which should be red) on the rendered page, you'll see an error message about the page not existing and a link to “Create this page”.
Click the “Create this page” link.
Edit your page and save it
Add a link to the page you created from the sidebar. When you click the link button, you can search for the page you just created. Or, you can copy the link you created originally.