I built a custom theme, and in it, there is a 404.php page and a search.php page.
Elsewhere in the template, I wanted to link to the search page directly. So, I used the get_search_template() function to get the search page link, which results in a link like this: http://example.org/search
When I click the link, I get sent to the 404 page template.
Why is it going to the 404 page template instead of the search page template?
Confusingly WordPress does not have a concept of a simply search page, it only has concept of search results page. The difference is critical because search without search query 404s as you are seeing.
If you want dedicated search page you would have to implement it as custom one, see Codex > Creating a Search Page.