Matrix servers keep a copy of any remote room an account on the server has joined, and it’s possible to recreate a room from the copies held on different servers. There are more details I don’t remember, but at a high level that’s how it’s distributed.

Storing messages of remote rooms in addition to local rooms is why people complain about the storage requirements of Matrix servers. They don’t realize it’s distributed.