What Information Is Lost by Histogram Equalization?
The expectation of information is called entropy. The loss of information can hence be understood as difference in entropy between source and processed image, assuming no random effect was added. 

Together with my answer on why contrast is not an appropriate measure of entropy, this gives us the simple answer:

The loss in information is simply the number of bits necessary to count the different images that have the same processed image (i.e. after histogramm normalization).

Now, the math here gets pretty different whether you assume that pixels have real-valued intensities or discrete ones. 

In the continuous case, you'd want to realize that histogram equalization applies a function to the pdf of the intensity, thereby adding negative differential entropy.

In the discrete case, multiple intensities of the source image will be mapped to a single intensity in the output: You can make statisitics of these ("empirical CDF") and from that derive how much information you lose.