How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?
Babbage's arithmetic unit (ALU) for the Analytical Engine was originally called the mill. It wasn't constructed out of binary logic gates (AND, OR, NOT). Instead it works on the basis of counting gear teeth and escapements.

The mill is essentially an entire Difference Engine designed to be mechanically controllable/programmable (rather than needing humans to set the input gears to the correct number). The Difference Engine is much more primitive than what we would call a "calculator" today. It is bascially a mechanical abacus. Only, instead of beads it represents numbers by the rotation of gears.

I haven't tried building one so can't quite tell you the exact detail of how it works but in general it works like this:


Two rows of input gears are spun to set it to two numbers.
The gears are connected together in such a way that when you rotate them one "cycle" both will rotate another row of output gears to produce a result. Note that a "cycle" literally means what it means - there is a crank on one end of the machine that you rotate with your arms one round to get the result.
The operation can either add the sum of the input gears or it can subtract one input from another.


That's all it can do, nothing else.

Given that it can do addition and subtraction, and given that we can calculate multiplication by repeated addition and division by repeated subtraction, we can perform any calculation.

In reality Babbage optimized his mill to do more than simply add or subtract (though, the machine can indeed do that). The gears are stacked on top of each other with the output of each stage being used as input for the next stage to calculate polynomials (somehow, I don't know the details). So you can arrange the output rows to represent multipliers in a polynomial equations and you can cycle the mill x number of times to get the result for f(x). But that's more to do with the Difference Engine. The mill for the Analytical Engine could do less specialized calculations.

So Babbage didn't design his "logic" the way a digital designer would design a circuit. He designed it the way a Swiss watch maker would design a complex feature for a handcrafted watch (moon phase display for example).