The mouse wheel is so integral to my mousing experience now that it's difficult to imagine using a GUI without one. Although I clearly remember using mice without scroll wheels, I can't recall exactly when the transition occurred-- when mouse wheels became a standard, expected feature on every mouse as they are today.
The first reference to a mouse with a wheel I can find is the Genius EasyScroll mouse, which was released in 1995.
With those terrible aesthetics, it's not surprising that mouse wheels weren't truly popularized until the first Microsoft Intellimouse was released in 1996.
I would argue that the mouse wheel is the first true mouse innovation since the invention of the mouse itself. Given its importance, I've often wondered exactly how the mouse wheel was invented, but I could never find a source of any kind.
Matt Young was kind enough to forward me a link finally revealing who invented the mouse wheel: Microsoft's Eric Michelman, as described in his article The History of the Scroll Wheel:
Back in 1993, as I was watching many Excel users do their work, I noticed the difficulty they had moving around large spreadsheets. Finding and jumping to different sections was often difficult. I had the idea that perhaps a richer input device would help.
My original idea was the zoom lever. This was simply a lever, presumably for your non-mouse hand (i.e. on the left side of your keyboard if you're right-handed). When you push it away from you the spreadsheet zooms out. When you pull it towards you, it zooms back in.
I prototyped this by hooking a joystick up to my computer and using DDE to connect it to Excel for zooming. Using a joystick button along with the stick, I also had it do "data zooming", which was drilling in and out through Excel outlines.
This all seemed useful, so I showed it to the Hardware division at Microsoft. They were initially cool to the idea, which I presented as a zoom lever, and it didn't go anywhere at that point.
At this point most people thought it was kind of wacky. Focusing on zooming was a very Excel-centric approach. More specifically, it was a very 2-D centric approach. That is, using an application that presents 2-dimensional data, like a spreadsheet or graphics, it's very useful to zoom in and out. But the other main style of application is a linear flow application like Word, and there it's not as useful. You could do zooming with Word, where zooming out shows you a multi-page view and then you click on a desired page and zoom into it, but that's not as natural as with a spreadsheet or graphics and images.
A number of people suggested adding panning and scrolling functionality. In particular I remember Chris Graham saying zooming was just too limiting and it should pan as well. In response to this feedback, I added panning to the prototype, so moving the joystick side-to-side and back-and-forth scrolled Excel in the corresponding direction.
Around this time, the hardware guys came back and said that they had considered adding a wheel to the mouse, but they didn't know what it would be used for. Document navigation answered that question, so they said that if I could get Office to support it, they would build it. This really meant Excel and Word since they were the "800 lb gorillas" -- if Excel and Word supported something, then the other Office apps would follow, and if Office as a whole supported something, then everyone else would follow too (this was the early 1993 when Office was the heart of most people's computer usage).
Eric was completely fixated on the idea that the wheel should be for zooming by default, but finally relented when he met resistance from legendary technology journalist Walt Mossberg. Before they shipped it, they added a button under the wheel, and made the default wheel action "scroll".
The rest, as they say, is history.
After that, mouse wheels-- and the third mouse button under the wheel-- quickly became popular, standard features on every mouse. Although work started on this feature in 1993, and the hardware didn't ship until 1996, the first mouse wheel patent filing from Microsoft is dated 1999.