I am unsure to what extent Mastodon search federates. But I did hear somebody refer to it as federated. I think the idea was that all searches take place on your own server, and only searches content that has federated to it already. That's also why they rely on "it's illegal to look for my post on your server" permissions; which I'll call out for the snake oil that it is. It might be your content, but it's on my server and you can't physically stop somebody from doing anything they want in the privacy of their own home. My goal was to provide something that's fully integrated with opensearch and also lets you search remote servers (assuming you authenticate and/or have permission to do so). The next step would be to build a distributed search engine to let you search through your followers' sites (which might take several minutes or more to return results) and then a background task version to extend that to the known fediverse (which conceivably could run overnight). I didn't get to that before I hung up my developer hat -- as I decided I needed to live more of my life before it's all gone.
M