A lot of the programs actually install the needed files in the root directory (C:\) or make a new folder and put it into the Program Files. Sometimes it easy to spot the folder or file in the root directory, but deleting it is another story.
A lot of times, when you go to delete the file, it won't let you because the file is in use.
To help find the offending program, you can run the Task Manager and see a list of processes running. Be careful with this, but you can end the processes that shouldn't be there and you may get lucky so that you can now delete the file.
Doing it this way may only help you until you reboot, and then it all happens again because of references in the registry that need to be deleted. However, once you find the file it will be easier to look up on the web how to delete it, rather than just guessing. This works a lot of times to get rid of those dialers and popups though. Or you could just stop going to unknown porn sites (just kidding

)
You don't need to reformat your hard drive or anything, just need to know what you are doing. Be careful about installing helper applications for your browser, as this is where they usually come from, or just not paying attention to what you are clicking.
Oh yeah, most of the time those dialers are illegal and can be disputed with your phone company. Some will dial to a foreign country and charge you an insane fee. If you think it already may have happened, you may want to call your phone company.
Its probably faster to reformat your computer most of the time though, but I think its fun finding weeding out the programs and I don't have to worry if everything is backed up. Always back important stuff up and be prepared to lose everything on your computer at any given moment, but everyone knows that.
-murph