How can I make my game (right now just a C# Console Application) appear in the Start Menu under Games??
I mean is it possible for any program to register as a Game in Windows Vista / 7?
Turn to MSDN for all your Windows answers!
Integration with Games Explorer requires that you author a game definition file (GDF), which is an XML text file that is embedded within a binary file (an executable file or a DLL) as a resource, along with a Windows icon. The game must then be registered with Games Explorer.
Details on integrating with Windows Games Explorer are provided in the DirectX SDK. The DirectX SDK includes a game definition file (GDF) editor, as well as an example GDF that is included in GDFExampleBinary, a sample. Another sample, GameUxInstallHelper, provides routines for integrating the required functionality into existing installation systems. The Game Definition File Validator (gdftrace.exe) provides debugging support for evaluating a GDF. Also see "Windows Games Explorer Integration" in the DirectX SDK Documentation for C++.
There is another article too, "Windows Games Explorer for Game Developers", which might provide additional information, especially if you use an InstallShield or MSI installer. It looks like you can just integrate it into the installer.
Also this blog post looks like a really great tutorial; even though it supposedly applies to XNA games, I read through it and it looks like it would still apply to you! Especially pay attention to this:
Which brings us to our final task – the actual registration of the game. This stage is generally done by an installer such as Inno Setup or InstallShield rather than by the user or developer directly.
And that (integration with an installer) seems to be covered by the above Windows Game Explorer for Game Developers article. So I think, given this information, it should be pretty straightforward!