To put it bluntly, they had to implement a fuzzy logic analog computer based on hydraulics rather than a digital computer based on binary states:
As usual, How Stuff Works has a reasonable introduction to the basic concepts with enough vocabulary to kick off more detailed research if you're really interested. That link will take you directly to the breakdown of the hydraulic paths and the speed governor. Those are the core parts required to provide input to that analog computer.
If you look at the shift circuit at the very highest level, you can see how the analog computer is going to work. Vacuum states are generally interpereted as low load, off-throttle or generally as situations suited for higher gears. As the throttle opens, the transmission will tend to gear down. As the governor speeds up, the lower gears cease to be an option.
Slightly off-topic: If you have ever worked in any sort of device control situation, these sorts of pictures give you the creeping heebie jeebies. In any work that I've ever done, I need to know for certain what state the machine is in and what's going to happen next when I provide my input. An analog control computer made out of metal and oil? Ick.