The Windows Version is important to know, but many have already posted steps that would work with Vista, 7 and XP.
XP being the most dangerous in terms of pop-ups as Vista and Win 7 have a lot included, for example codecs to play music recorded in different formats.
If you have kept your computer safe with an Antivirus Solution from the beginning and you received update notifications, they are most likely legit as your Antivirus has already added your programs to the safe list.
I would just like to point out, that Microsoft Updates, come encrypted from the Microsoft servers, that and the check process that Windows performs on their own Windows update application on your computer prior to notification, makes it 99 percent safe.
But the process is different on XP, because XP is not as secure as Vista and Win 7.
On XP, you have to use the browser to check for Updates Manually, and even the downloaded update application from their own website could be compromise.
Yes - XP comes with it's built in Update Application, but in order to received certain updates that application has to be updated when you visit manually the Microsoft Update Site, or they download to your computer where that application has to be updated in order to received updates that the old updated can't handle.
Something that Vista and Win 7 handles inside your computer with User Account Control, Windows Defender, Ramdom Acess Utilization and DEP.
All these defenses on Vista and Win 7 makes it harder for a laptop or destop notification to be malware if you intall the program from the beginning.
As this same protecting processes, were making sure that the intallation of those products you did, actually have a legit certificate or signature which is verified by the Vista or Win 7 Operating System.
Now, like I mentioned above, Win 7 has many codes for music and Video, making it less likely that you need one as you are browsing the internet.
For this reason, is that the worst pop-ups happen on while you have the browser open and browsing the internet and those are the most likely to infect your computer.
As was mentioned by another poster, don't use the OK, Cancel , or RED X, to close broswer pop-ups, use Windows Task Manager, by right clicking on your TASKBAR - Tab named Applications and kill them all.
This buttons are commonly program to initiate the download of malware, but killing them with Task Manager will stopped them.