Where in the registry does Windows store with which program to open certain file types?

The open with associations are all stored in HKEY_CLASSES_ROOT.

This is a special registry hive that combines the local user's associations in HKEY_CURRENT_USER\Software\Classes with the system's associations in HKEY_LOCAL_MACHINE\Software\Classes.

Here's a shot from my registry for the PDF association you mention in your question:

Just to extend Gareth's answer:

From playing with the registry it looks like

• entries from HKEY_CURRENT_USER\Software\Classes override entries from HKEY_LOCAL_MACHINE\Software\Classes in the HKEY_CLASSES_ROOT\Software\Classes
• setting file's extention association from command line using assoc command acts upon HKEY_LOCAL_MACHINE\Software\Classes
• setting file type association from command line using ftype command acts upon HKEY_LOCAL_MACHINE\Software\Classes

While the answers are (probably, I didn't check) correct, the sane way to modify file associations is with the GUI Microsoft designed for it. (That is, if you are a user and not a setup developer.)

Here is one tutorial with nice pictures, I found it with google: http://www.digitalcitizen.life/how-associate-file-type-or-protocol-program

But you can just open start (win7 menu or win8 screen, doesn't matter) and type file association, enter and it should open the correct control panel link. (Control Panel\Programs\Default Programs\Set Associations).

The problem with many of these methods is that Windows doesn't really handle the possibility of different executables having the same name. When using the GUI, there is no way to know to which one they are referring.

That is because, in Win 7 anyway (I haven't checked win 10), the default program for explorer is stored in HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\FileExts\ But if you look there you will find for example in the OpenWithList key, something like LibreOfficeWriterPortable.exe in my case. But I have multiple versions of that program, all with the same name, so changing that key is not going to help.

To find what it actually points to, you have to go to (in my case)

HKEY_USERS\S-1-5-21-966747605-1980359026-2421819745-1000\Software\Classes\Applications\LibreOfficeWriterPortable.exe\shell\open\command

to find out what that will actually open, i.e. what the named they are using actually points to.