I concur with the other answers above; the icon comes from the police inspector/detective stereotype, as shown in some very well-loved cartoons:
Image from Search-Best-Cartoon.com
Image from Tim's TV Showcase
For the most part, most computer systems buried the find/search function in menus (meaning it often had no icon at all). It was really only on devices and systems that emphasised highly visual iconography (like PDAs) that an icon was developed for it.
One of the interesting problems with any of the icons below is that a tool that uses a magnifying glass icon (or even binoculars, see below) can be conceivably mistaken for one that magnifies text on screen (especially since most operating systems supported such a function from early on), leading to the very weird situation we have now (here's the Windows Magnifier icon in Windows Vista):
Image from Wikipedia
…and these icons are also often used to zoom in and out respectively (this rather convoluted example comes from Apple's built-in Preview app and shows the zoom out, actual size, zoom in and search toolbar functions all using magnifying glasses for their icons):
Early examples of the icon in use
Some historical examples of this icon in use:
NeXT Inc. Workspace Manager
This example dates to the late 80s (the very first edition of what would become NeXTSTEP).
Image from Typewritten Software's excellent gallery of old and obscure OSes
Apple Newton OS
The original Newton MessagePad (released in 1993) was (to my knowledge) the first product to use the icon:
Image from Newton Gallery!
Apple's Newton OS used the icon as a persistent icon for find specifically. From the New Features of the Newton 2.0 Operating System manual, Apple says:
Tap the Find button 🔍 to search for items in selected applications.
Screenshots from PDAdb.net
Palm OS
The original Palm Pilot 1000 (and later Palm OS devices) used a very similar find icon:
Images from Wikipedia; 1, 2
Apple Mac OS 9
Mac OS 8.5 introduced a feature called Sherlock intended to make finding files easy. While its app icon and UI didn't include a magnifying glass (instead it relied on the icon of Sherlock Holmes' classic deerstalker), it did creep into a lot of the supporting marketing:
Photo by Federico Giacanelli
Photo by Max Pictures
When Mac OS 9 came out, including with it a wholly-revamped update to the app (called, appropriately, Sherlock 2), Apple went "all in" with the magnifying glass iconography:
Photo from Amazon.com
Microsoft Windows 95
Before Windows 95, the Search function was hidden away in a menu (meaning it didn't have any icon).
In Windows 95, with the advent of the Start menu, the renamed "Find" function got the now-familiar icon:
Image from Wikipedia
The icon was also used for the new Windows Explorer icon as seen above (which had previously been called "File Manager"). The new icon brought it into line with the Internet Explorer icon which hadn't yet turned into the lowercase e we all know now.
Friend Finder
Legendary icon designer Susan Kare designed an icon for an app called Friend Finder which features in her book of icons:
Notable Alternatives
Some alternatives to this (now ubiquitous) icon for searching over the years include:
Binoculars
As used in the original Mosaic Netscape and the next few versions of Navigator, as well as—briefly—in Microsoft Word
Torch/flashlight
As used in Netscape Navigator 4 and Netscape Communicator
A dog/hound
As used in the Windows XP search assistant, and the original Dogpile.com search engine logo)