The first thing to do is to backup anything he's done himself, wipe the drive, and reinstall an operating system. I'd recommend one of the more user-friendly Linux distros (like Ubuntu) if all he does is email, web surfing, and light word processing (like my mother-in-law), but if he wants to run something not available on Linux (very common), reinstall Windows. Seriously, if he's getting advertising popups out of nowhere, his OS is seriously compromised, and half-measures are unlikely to remove everything.
Assuming this is a halfway recent version of Windows, removing or disabling Internet Explorer will do nothing. IE nowadays is something of a shell program, since Windows includes services like HTML rendering. These are used by applications and other parts of the operating system, and you're not going to get rid of them.
One thing to consider is installing another browser. Firefox is good for this, because it has a lot of defensive plug-ins you can get. NoScript (my favorite) requires a certain very basic grasp of how computers work, which many people don't seem to get, and your brother might be among them. However, AdBlock Plus may stop some of the adware.
There's the usual list of things to recommend to your brother. Like what sites he surfs, although (a) he presumably surfs them because he wants to, and (b) there was a recent adware problem on the New York Times site, and so no site that sells advertising is safe. Or being careful what he clicks on. Have him keep his Windows updated, and make sure he has good AV software.
Unfortunately, the bad guys are increasingly clever, and it's getting increasingly hard to set up a Windows box that's halfway safe for the average surfer. You may have to go through this again.