Is it possible to clean up PlayerPrefs when a user uninstalls my game?
Also, what are the best installers (install wizards which help people install\uninstall the game)?
Thanks 
.
Check out the docs for playerprefs:
That will show you where the actual preferences are stored. On Windows, it is in the registry. Note the specific key used and set your uninstaller to remove it.
I have successfully used NSIS ( NSIS Wiki )for installer/uninstallers on Windows. It is free and super powerful, though not always as easy to use as some of the other ones. It is well worth the time it takes to get to know how it works.