It's gotten so that any time I see something new from Google, the first thing I do is check if I can even use it. Often I am disappointed. I still can't use Fi, and Google Now is almost useless because it refuses to use my email to customize itself.
Go to the Google Apps Admin Console (https://admin.google.com/AdminHome).
Navigate to Apps > Additional Google Services
You'll see a gray bar at the top of the screen ("Filter: Top featured services"). Click the "X" on the top right to disable that filter.
Scroll down to "Web History" and select "On for everyone."
Each user may then need to also enable Web History for his or her own account (https://www.google.com/settings/accounthistory/search).
No, it shouldn't be that hard, but, yes, that will work.