I wonder how discovery and search work if it’s just a bunch of linked documents? Do search engines exist outside of Gemini and link into it?

There are several search engines of Geminispace, running as Gemini servers. There are also a number of feed aggregators that are widely used.

The protocol supports query strings so the server can generate content based on the string, which can be used for an in-Gemini Gemini search engine. It doesn't have to be all static content. People could also build out a directory (like the now defunct DMOZ and similar directories for the Web).