Well, a program uninstaller is just the reverse of an installer with some additional considerations. A installer copies files and makes changes to the registry. Fundamentally, that is the only thing that needs to be removed. There are additional considerations involved for files that were made while the program was installed, such as configuration or data files- you wouldn't want all your word documents or excel spreadsheets wiped when you remove office, for example.
Anything that uses Windows Installer (.MSI) automatically can have a uninstaller. The uninstaller is created when you install the program and is created to rollback the Installation. They can be set to automatically detect previous installations and either require them to be uninstalled by the user first, perform the uninstallation before continuing, or even patch upgrade the existing one. This all depends on the settings used in the MSI authoring tool.
Honestly, the problem is not that it's hard to uninstall anything from the perspective of a software creator; the problem is that software companies don't want you to uninstall their product so they cloud that process in ridiculous special steps. Just consider any AV software. They often claim that "because it's low level software, you need special tools to remove it" Well, that's a pretty hollow statement since you don't need special tools to install it. You only need "removal tools" because if they add an extra step it's more likely people will miss it and essentially keep their product. Another is that it feels "wrong" to make easily removing their software "easy". They include extra steps, use it as an opportunity to receive feedback. When I want to uninstall a program- I want it gone. I don't want to fill out any stupid surveys, or have the uninstaller open a tab on my browser to "ask me why". Market research is THEIR job, not mine. If they want to figure out the issues with their program, they should have a QA team, not redirect me to a page with a sad face emoticon trying to make me less apathetic.
Java is another oddity, for some reason they never uninstall previously installed versions, supercede settings and take over for those previous versions, but a bunch of application-specific settings can still use the older virtual machine, and then if you have multiple VM versions running weird stuff occurs when Java uses it's reflection libraries. The odd thing is they practically have to be leaving those old versions around on purpose- surely any level of actual QA investigation would have come to the conclusion that they don't actually need multiple Java versions installed. At the very least it might make sense to prompt the user- with a default checked option- to uninstall the previous version first, right in the installer. Only developers or people that know they will need a specific version are going to keep multiple VM installs anyway. I suspect it might have something to do with their whole Ask toolbar thing, possibly as some sort of requirement.
