DES hardware implementation of substitution lookup table [ ReWorked ]
A simple way to think of the S-boxes of DES when it comes to a hardware implementation is: 8 independent ROM ICs, each with 6 address input lines and 4 data out lines. In an educational physical implementation with retro standard ICs, two such ROMs fit a 4 kiB EPROM (a 2732). Some actual software implementations of DES do group S-boxes two by two in order to reduce the number of table lookups.

Another way is: 8 times, 4 independent boolean functions of the same 6 input bits; for a total of 32 independent boolean functions of 6 input bits out of 48 input bits (which themselves come from the key, with a wiring dependent on the round and if we are enciphering or deciphering). It is well known how to build any boolean function of 6 input bits (e.g. using Karnaugh maps), hence in principle build these 32 boolean functions. However Karnaugh maps do not yield efficient/compact circuits in the case of DES S-boxes.

There is little exploitable regularity in the DES S-box functions. The most striking one is that each line of numbers of the spec of the S-box values (FIPS 46-3 appendix 1) is a permutation of $\{0\dots15\}$.
It follows that we can model each of the 32 boolean functions by: 4 functions of 4 input bits (coding columns on that spec) set for precisely 8 out of 16 combination of these 4 inputs, followed by selection of the appropriate of the 4 results of these 4 functions according to 2 other input bits (coding line in the S-box).
This translates into a trivial systematic construction of the functions using NAND gates with at most 8 inputs, of depth 3 (including input inverters) plus the final 1-out-of-4 multiplexer stage.
Using this structure, it is very easy to fit two S-boxes in a generic PAL with 12 inputs plus internal feedback and 10 outputs, at least 8 of which having at least 8 input terms. The once-popular PALCE22V10 is ample.

The problem of minimizing the complexity of these 32 functions, including considering that they are evaluated together and some work can be shared among the 4 functions belonging to the same S-box, has been extensively studied; for example by Matthew Kwan: Reducing the Gate Count of Bitslice DES, 2000, eprint 2000/051; however he is focusing on 2-input gates and considers XOR of unity cost, which is fine for software, but hardware has different constraints.