What exactly is whitening?

Whitening your data in this context essentially means rotating into space of principal components, diving each dimension by square root of variance in that direction, and rotating back to pixel space.

Assume you have an NxD data array X that holds your patches. Here is how they were whitened in Coates et al paper (MATLAB):

C= cov(X);
M= mean(X);
[V,D]= eig(C);
P = V * diag(sqrt(1./(diag(D) + 0.1))) * V';
W = bsxfun(@minus, X, M) * P;

The full code can be downloaded here: https://sites.google.com/site/kmeanslearning/home or directly from Adam's page http://www.stanford.edu/~acoates/

Alex Krizhevsky (from Toronto) also uses this procedure in his "Master's Thesis" http://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf and gives a little more details and some motivation. (see Chapter 1.3 and Appendix A)

Qualitatively, this "erases" the boring stuff in your image (by subtracting the usual mean, and getting rid of the correlations in pixels that are there in almost every image), and leaves behind the "interesting" parts. I realize that's super vague but that's the intuition.