If the popup you saw that said "Microsoft updates are available" came from an icon that looked like a little gold shield in your System Tray at the bottom right, that's what's supposed to happen when Microsoft has an update that you should have. It should happen only for Critical Security Fixes, and generally you should let them download them and install them.
If you click Start, and there's a "Windows Update" or "Microsoft Update" in the list, you can click it and go get one you might have missed. If your start list doesn't show one or the other of the update links, you should use the link posted at 08 May 06 - 11:52 PM to go to the update site, get available critical updates, and (I recommend) sign up for automatic updates.
The link should be at http://windowsupdate.microsoft.com/, but they've recently started "redirecting" to the Microsoft Update, instead of the Windows update site. Either should work for you.