I'm assuming he landed somewhere after the search that his bosses had logs for, like maybe a bio page on some .mil domain. Back in the 2000's, you still got a referrer header that included not just "google.com", but also the search query parameters.

So if you followed https://www.google.com/search?q=my+asshole+boss+joe+schmoe to get to the .mil hosted bio page, they got to see that.