You can access the data search from our search page, or from the search field in the upper right corner of every MusicBrainz page (which uses indexed, non-advanced search).
The indexed search is used by default. It uses the Lucene search engine, making it much more powerful than a direct database search, and, if the "advanced" option is chosen, allowing all kinds of specific queries via its advanced search syntax. It's biggest downside is that it can't find results that haven't been indexed yet, which means it won't always find anything added less than 3 hours before.
The direct search searches the database directly: it can only carry out simple keyword searches with no boolean logic, but it is always up-to-date.
Note: It is just a fallback method in beta, in case something goes wrong with the new search server.