They store all the messages in a some sort of distributed append-only graph database, which theoretically makes it a bit more fault-tolerant and censorship-resistant, but which does not work very well in real-world use cases. In addition to performance issues, it makes it very hard to filter out all sorts of abuse on public channels before it reaches the clients. In a rather bizarre turn of events, they implemented a kludge solution (1) in which all the messages are routed through a central server, and after then, passed on to the distributed database.
1) https://matrix.org/blog/2025/04/introducing-policy-servers/