Starting a page from a link, or after a search
To start a new page, you can click a link to the new page. This takes you to edit mode of the non-existing blank page, which allows creation. You will not be able to create a new page unless you are logged in.
Another way to start a new page, is to perform a search for the new title with the Go button (as you should have done before). When the search finds nothing, press "create the article".
Links to non-existing pages are common. They are typically created in preparation for creating the page, and/or to encourage other people to do so.
Links are not only convenient for navigation, but also make people aware of the new page (those who read a related page). New page links are not really broken, as long as the name correctly identifies the intended content.
Of course, you can also create the link yourself, in a related page, index page or your user page. However, it may be better to wait with creating links until after creating the new page, especially if the new link replaces one to an existing page. In this case, create the link but press Preview, instead of Save. From preview area, clicking the new link will create the new page (without updating the referring page).
If you want to know more, you can look to the Wikipedia instructions to the Start a New Page - small trick - in the left column of this Wikipedia page you can select also the same page in your language.