What does it mean when a game is labeled "Games for Windows"?

The "Games for Windows" scheme is Microsoft's attempt at regulating the PC games market in a similar fashion to how the console games markets currently are. Any game carrying the banner has to meet many technical specifications, including compatibility with the latest versions of Windows available at the time of release, and it has to have undergone and passed a rigorous testing process. See here for Microsoft's official description.

Additionally, some games are labeled "Games for Windows LIVE" and those games allow you to connect to the Windows Live service (which most people associate with Xbox Live, it's the same thing). Games labeled as such allow you to get achievements worth points towards your gamerscore, see your friends online and chat with them, etc. Some people use this as a method to pad their gamerscore with points, as you can, for example, buy Fallout 3 for both Xbox and GFWL and get twice the point credit for playing the same game.

It's a brand owned by Microsoft. Those game are certified by Microsoft to work on Windows (introduced with Vista in 2006)

http://en.wikipedia.org/wiki/Games_for_Windows

Apparently there are also port forwarding requirements for multiplayer play under this system. This can be a deal-breaker if you're trying to play it behind the same NAT'ed firewall.