The registry is like a big book of keys and values that windows stores, about 30-50MB in size. Lots of programs use this book to record all sorts of stuff, records of the add/remove program list, what files extensions are associated with what programs, CD keys, and lots lots more.
Messing with the registry is rather dangerous if you don't know what you're doing.
Here is the MS help link for manually removing the add/remove programs listing:
http://support.microsoft.com/kb/314481
There is also a pretty and easy to use tool for editing the add/remove programs list here:
http://www.softpedia.com/get/Tweak/U...e-Master.shtml
There are other registry entries besides the add/remove programs listing, usually under HKEY_LocalMachine/Software/Company, game ect. Presumably a registry cleaner is a much safer thing to run after deleting the files and add/remove listing than manually going in and deleting stuff from the registry.