It all started in Windows 98 with the launch of Windows Update; they then released the Critical Update Notification Tool (later renamed to Utility, for obvious reasons) which would query the website and just tell you when a critical update was available to go check the site.
Otherwise, in the 95 era, I believe you'd likely be finding out through a software vendor or otherwise that a certain fixpack from Microsoft might fix an issue and you should go grab an update then.
Um… what? You would trigger online updates in Windows 95 OSR 2 by using IE and navigating to the Windows Update website. This would then would trigger the updater.
That was all after the fact. For its initial release and even much of OSR 2 the only updates you got came with a new computer via the OEM updates of which OSR 2 was the big one. If you were lucky you might see a Service Pack on CD though that was more of an NT/2000 thing.
Yeah -- OSR 1 (95 A), 2/2.1 (95 B), and 2.5 (95 C) were just that - OEM Service Releases.
Anything else would have been a direct fix package - such as the DCOM95 OLE Update, DUN 1.4, or Winsock 2 -- things that you only installed if you needed something that used those functions, and often would become bundled with the software anyways because users might not have been given those updates out of the box.
There was at least one XP-era update CD that I do recall - the Windows Security Update 2004 contained patches for 98 through XP and was available by mail from Microsoft.
This is supported by the wikipedia page for Windows Update:
"Critical Update Notification Utility (initially Critical Update Notification Tool) is a background process that checks the Windows Update web site on a regular schedule for new updates that have been marked as "Critical". It was released shortly after Windows 98."
Unfortunately, the citation for that is no longer active on MS's site, and the archive.org version no longer works either.
> Windows Update was introduced as a web app with the launch of Windows 98 and offered additional desktop themes, games, device driver updates, and optional components such as NetMeeting. Windows 95 and Windows NT 4.0 were retroactively given the ability to access the Windows Update website and download updates designed for those operating systems, starting with the release of Internet Explorer 4.
— Software could not expect internet connection (or any network at all) to be available, and would be considered really arrogant if it tried to dial or spend user's traffic by default.
— Those who knew how to enable those features probably checked update sites and news sites manually often enough.
— Almost all software had to bundle required components and updates anyway. Games came with DirectX version 5/6/7/8/9 installers, IE version 4/5/6 installers provided important system components, acting as semi-service-packs for 9x systems… and, of course, Visual Studio library dependencies.
