What happens if a department runs out of space? I'm curious what happens if a department runs out of space - e.g. they are expanding, but they don't have enough rooms for their faculty, postdocs, visitors, etc. It's presumably possible to squeeze a bit, put many PhD students into the same room for example, but this would be a short-term solution.

The obvious thing to do seems like to petition the dean to allocate more space to the department, but this seems very nontrivial. For example say three departments currently occupy 3 floors each in a 9-floor building. If one department needs more room, the clearest way to do it is to give them another floor, but that would force the other two departments to contract and/or shift some of their personnel to a different building, which might negatively impact their performance.

Similar things must surely have happened multiple times in the past. What usually happens?
There is no "usually". There isn't a worldwide academic rulebook that states what happens when a department runs out of space. This is extremely dependent on the university, the department, who runs each, the current power balance between the different departments and the university, the university's budget, the culture of the research field and the country... Academia isn't different from the rest of the world, how would you even start to answer a question as vague as "what happens when a company's department runs out of space"?!