How can DES have 6x4 S-Boxes and still be reversible? Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?
DES is a Feistel-based cipher. In such ciphers, the function $\rm F$ need not be invertible. Here's the reason:

In each round, the following operation is applied: 

For $i =0,1,\dots,n$

$L_{i+1} = R_i$

$R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$

Decryption is performed as follows:

$R_{i} = L_{i+1}$

$L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$

As you can see, the decryption does not need $\rm F$ to be invertible. (Since the decryption does not need to compute $\rm F^{-1}$.)