Nowadays, with the more enterprise-y features (policy, etc.) of the {Gmail,Apps} for Work, I at least get _why_ they're not on parity. But if you asked me 5 years ago, I would have never guessed this (Apps users missing out on XYZ) would still be a thing.
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.
How did you set it up?