How do I have to imagine $p(m|x_t,u_t,x_{t-1}$)? In his book, he kind
of just handwaves it...
In SLAM, you need to build two entities, the robot's state (i.e. position and direction) and the map. In deterministic approaches, the probability of both robot's state and the map is one, meaning you know these entities with an absolute true (i.e. zero uncertainty). In probabilistic approaches, you can't know the robot's state and the map with an absolute true that is because sensors have noise, therefore, the probability principle is the right choice to handle this kind of problems. Now what is this probability $p(m|x_t,u_t,x_{t-1}$)? This is a conditional probability, the inputs are the previous state of the robot, the current state of the robot, and the current control input that drives the robot whereas the output is the probability of the map. Remember the probability here reflects the certainty of the knowledge about the map. For example, if the probability is 0.9, it means we are 90% sure about the location of the map and 10% is the uncertainty.