Ridiculously complex is about the size of it!
But yeah, at the fundamental level, you only need a few very simple primitives to build a computer. As cwthree says, at the abstract level, the basic binary logic operations are sufficient; in fact, you can get away with only a single operation if it is functionally complete, like NAND.
So the trick to building a Dwarf Fortress computer would be coming up with designs for the fundamental components (logic gates) and the components derived from them, like I/O and memory cells. And then, of course, getting your dorfs to actually build thousands of those components, and keeping them sufficiently well supplied with booze during the construction so they don’t snap and bring the whole project down in an orgy of manic-depressive rage and violence. 
Of course, Dwarf Fortress gives you a lot of things to play around with, so just designing a DF NAND gate and then deriving the rest of your computer from that would be incredibly inefficient. A lot of things you should be able to build directly. There is a breakdown of the design of a lot of the basic components in the Dwarfputer Project Sheet which is linked to on that DFMA page. It looks like his memory cells, for example, are implemented with fluid pumps and hatches to regulate the amount of water in a recessed area. If there’s enough water in the cell, it contains a “1”, otherwise it contains a “0”. A memory cell can be queried by applying power to one of the gear assemblies attached to it, in which case another of the assemblies, one designated as output, will become powered (or unpowered) depending on the water content.
Another component is the decoder. This is a unit that takes as input an n-bit number (IOW, it was n “input wires”), and depending on what that number is, activates the corresponding one of 2^n “output wires.” Here is a simple 2-bit decoder, built using only AND gates and NOT gates. If the inputs {A0,A1} are equal to {1,1} (binary for the number 3), the output wire D3 will be “on” and all the others will be “off.” If the input is {0,0}, output D0 will be on and D1,D2,D3 will be off.
A decoder is useful in many, many ways, but one way in particular is to translate a memory address so that a line going to the correct bank of memory cells is activated. For example, Jong’s Dwarfputer has 256 bits of memory that are arranged as 32 eight-bit “words.” So his design uses a 5-bit decoder (5 inputs to 32 outputs). To retrieve the contents of memory address 25, the number 25 is sent as the binary signal “11001” on the five wires of the address decoder. The address decoder then activates its 26th output wire. That output wire is physically connected to the “read” inputs of a whole row of eight memory cells – so now each of them will transmit their contents onto the waiting memory read bus.
There are many, many more little details, of course, but they’re all variations on the same basic gates. It would probably be easier to just give you a basic overview of simple microprocessor design, and then talk about how the various fiddly bits could be implemented in Dwarf Fortress. How deep is your curiosity?
