RPM has an erase option that's supposed to work
Depending on package type and distribution the answer is yes.
You can install/uninstall rpms in kpackage,rpmdrake,YaST2.
Some well-packaged tarballs have an uninstall script,others dont.
Slackware and Debian have uninstall options with thier package management systems.
What distribution of Linux are you running?What kind of package do you want to uninstall?