Google Spokesperson:"For Google Apps customers, the domain admin can disable services such as Web History for the entire domain in the Google Apps control panel. This message means that Web History has not been enabled for your domain and your account."
In case that's still not clear, and it probably won't be except to users of Google Apps, there are different rules for Google services aimed at businesses or that let businesses pay a certain amount per month to use Gmail as their corporate email systems with all the domains and addresses customized with the name of their business rather than Google's.
IT administrators have a certain amount of control over those apps, one aspect of which is being able to choose how nosy Google is allowed to be when it is private-labeled and kept on a leash rather than operating with a free hand from the mother ship.
Ultimately, either your company wanted to limit the snooping, or your employer simply doesn't care about your deepest secrets, interests and desires; at least not as much as Google cares. Because your company only wants you to work; Google wants you to search, learn, browse, and, ultimately, buy the McDeepest Interest Holiday Present as its behavioral model for you says you should.
Currently you're free to buy or not buy. In the future, the behavioral model of you that Google builds will be so well rounded and self directed that if you turn down the McDeepest Interest package it told advertisers you'd buy, it might hunt you down to beat you up. (Recently sentient behavioral models are marvels of technology, but everything they are comes from someone else, so they're really, really insecure and easily offended. This is the real reason most hardcore geeks want to keep big companies from building such elaborate models of them. Most geeks can't fight and it would be really embarrassing to be beaten up by an artificial model of yourself.)
- "Mine had no delete button. It just had "No Thanks" or "Turn Web History On"...am I good to go then?"
That message appears to mean you either opted out of the Improve MySearch Results At the Cost of the Last Shred of My Privacy program when it was presented to you, or your account is so long-standing you got grandfathered into being un-followed.
- "Same here; should I turn it on and then remove history?"
No. It may be better to have loved and lost than never have loved at all. But when you're talking privacy, it's better never to have given one of the nosy crocodiles a taste of your flesh in the first place. Leave that history turned off.