How does Windows handle program dependencies?

It doesn't. Unless we're talking about .NET which asks you to install framework version X according with the compiler.

Everything else just throws an error. With luck, you get missing dll xxxx.dll. Although, most installers will have the required libraries included in order to run the software.

Edit 4/4/2014: Hey OP, look at what was just released today:

http://blogs.technet.com/b/windowsserver/archive/2014/04/03/windows-management-framework-v5-preview.aspx

I just wanted to expand a little on the accepted answer, because it's a little sparse on details. Filipe's answer makes no mention of the strategies that Windows actually does use to resolve or mitigate program dependency issues, like the component store (WinSxS,) the global assembly cache, the MSI system, etc. But on the other hand he's basically right in the sense that it's the developer's responsibility to include any custom libraries with the app, and check for the existence of dependencies before committing to the install transaction.

Windows is less modular than Linux, which has positives and negatives. On the down side, Windows is more monolithic, meaning comparatively fewer components of the operating system are removable or optional like in Linux. (Though Windows is slowly getting better about that.)

But on the up side, that means developers are able to make a lot more assumptions about what libraries a user will already have present on his or her machine. And various versions of those libraries, once installed, will be stored side by side in the component store, so that you no longer have App1 barking about needing crapDLL.dll, and App2 barking about needing a different version of crapDLL.dll at the same time, etc.

In Windows it is up to the software author to provide versioning for their libraries. Windows has a few facilities to help with this.

The Windows Installer and the Trusted Installer services which interact with installation programs (.msi). There is also some supporting technology called Isolated Applications and Side-by-Side Assemblies that help sort out versioning conflicts.

For .NET framework applications there is the Global Assembly Cache, Strong-Named Assemblies, and at the core Manifests.

In Windows 8 and 8.1 there is the Windows App Store along with the Windows Runtime Library (win32 API replacement).

edit: At the core of most of these technologies are assembly manifests, embedded files that provide version numbers, authors, dependent assemblies and their versions, amongst other data.