For a while, switching was done using electromechanical relays that established interconnect networks. A common setup at one point was the use of stepping relays that would be advanced from position to position under the control of the caller with each rapid pulse in pulse dialing - each digit would plausibly step one of these relays, routing the call from switch to switch until it reached its destination line and caused the remote ringer to ring.
A further improvement on this was the so-called two-axis switch which allowed selecting both an outgoing route and multiple outgoing "banks" from each switch to reach the next, improving the capacity of the exchange. As Wikipedia describes:
These [two-axis switches] were commonly used in telephone switching with ten banks of ten contacts. The coils were typically driven by the electrical pulses derived from a rotary telephone dial. On a two-motion selector, as a digit was dialed, the wipers would step up the banks, then automatically rotate (self-step) into the selected bank until they found an "unused" outlet to the next switch stage. The last two digits dialed would operate the connector switch (final selector in Britain). The second to last digit would cause the wipers to move up and the last digit would cause them to rotate into the bank to the called customer's line outlet. If the line was idle then ringing voltage would be applied to the called line and ringing tone was sent to the calling line.
At each stage, various conditions (such as a lack of outgoing banks) could be detected and reported. An example of such a condition is the "reorder" tone (or fast-busy tone, distinct from the normal busy tone) meaning that the call could not be processed through the network for lack of exchange resources. For example, if one of the above two-axis steppers failed to find an open bank, the caller would get the tone and the call would not be routed further.
This piece of audio demonstrates a pulse-dialing code which reaches various points in an exchange and hears different tones, before ultimately reaching the destination and finding the circuit busy.
At the same time, various signalling schemes such as the use of DC voltages and tones was used to coordinate the state of scarce shared resources such as long-distance trunks.