* search is currently available as a beta. At least mastodon.social and mastodon.online have it. If you check your server says 'v4.2.0-beta2' in the bottom left to double check.
If you are interested in how to opt-in, or some of the more advanced features, check out this post by @mastodonmigration : https://mastodon.online/@mastodonmigration/110957761613273404