It's never been an absolute policy, but they certainly used to prefer people with degrees; it's an easy filter when you've got a million CVs a year to parse through.

HR found it was useless as a predictor of success, though, and the policy was officially dropped last year:

http://www.businessinsider.com.au/google-hiring-non-graduate...

Keep in mind this was 2003, Google had less than 2000 employees then.