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.
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.