Detecting installed programs via registry

On 64-bit systems the x64 key is:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall

Most programs are listed there. Look at the keys:DisplayNameDisplayVersion

Note that the last is not always set!

On 64-bit systems the x86 key (usually with more entries) is:

HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\Windows\CurrentVersion\Uninstall

User-specific settings should be written to HKCU\Software, machine-specific settings to HKLM\Software. Under these keys, structure [software vendor name]\[application name] (e.g. HKLM\Software\Microsoft\Internet Explorer) may be the most common, but that's just a convention, not a law of nature.

Many (most?) applications also add their uninstall entries to HKLM\Software\Microsoft\Windows\CurrentVersion\Uninstall\[app name], but again, not all applications do this.

These are the most important keys; however, contents of the registry do not have to represent the installed software exactly - maybe the application was installed once, but then was manually deleted, or maybe the uninstaller didn't remove all traces of it. If you want to be sure, check the filesystem to see if the application still exists where its registry entries say it is.

Edit:

If you're a member of the group Administrators, you can check the HKEY_USERS hive - each user's HKCU actually resides there (you'll need to know the user SID, or go through all of them).

Note: As @Brian Ensink says, "installed" is a bit of a vague concept - are we trying to find what the user could run? Some software doesn't even write to the Registry at all: search for "portable apps" to see apps that have been specifically modified to run directly from media (CD/USB) and not to leave any traces on the computer. We may also have to scan the disks, and network disks, and anything the user downloads, and world-accessible Windows shares in the Internet (yes, such things exist legitimately - \\live.sysinternals.com\tools comes to mind). In this direction, there's no real limit of what the user can run, unless prevented by system policies.

You could use MSI API to enumerate everything installed by Windows Installer but that won't list all the software available on a machine. Without knowing more about what you need I think the concept of "installed" is a little vague. There are many ways to deploy software to a system ranging from big complicated installers to ZIP files and everything in between.