The story of CPUs is one of increasing amount of stuff per package.
The earliest CPUs always used serial ALUs built from a few relays or vacuum tubes.
The first to buck this tradition was the 1947 Whirlwind.
The earliest transistorized CPUs built everything from individual transistors.
The Apollo Guidance Computer (AGM), perhaps the first computer built from integrated circuits, used only one kind of IC outside the memory: 3-input NOR gates. The ALU and every other part of the CPU was built entirely from a large number of NOR gate ICs.
The (much faster) Cray 1 also used only one kind of IC outside the memory: another kind of NOR gate.
As people figured out how to cram more transistors on a chip,
later CPUs used (relatively) fewer chips to implement an ALU.
An ALU can be built entirely from multiplexers ("Multiplexers: the tactical Nuke of Logic Design"), using many fewer chips than the NOR implementation.
Dieter Mueller posted a 8-bit ALU design that has more functionality than two 74181 chips -- the 74181 can't shift right -- built from even fewer chips: 14 complex TTL chips: two 74283 4-bit adders, some 4:1 mux, and some 2:1 mux.
Like many historically important commercial computers, many home-brew CPUs use some version of the 74181, the first "complete" ALU on a single chip.
Many of those CPUs built a 8-bit ALU or a 16-bit (or both) out of a few 74181 chips and a few 74182 chips -- each 74181 only handles 4-bit-wide operations.
Homebrew machines typically use the simplest possible thing that will work -- the carry-out of one 74181 feeding in to the carry-in of the next, forming a ripple-carry adder.
Commercial machines that use 74181 chips typically use a 74182 look ahead carry generator to make addition and subtraction significantly faster.
Today most ALUs are hidden away inside some chip -- a small part of a CPU, some other kind of ASIC, or a CPLD or FPGA.
Even after "single-chip computers" were available,
occasionally someone will build a 74181-compatible ALU out of a GAL, or an ALU using only simpler logic gates, or even individual transistors or relays, for learning purposes.
People have done it, therefore it must be possible.
A step-by-step guide explaining ALU design and implementation sounds like a really good idea.
Please help us write one at the Microprocess Design wikibook,
perhaps the "ALU" or "Wire Wrap" sections.