Where exactly are the apps shortcuts in the Windows 8 Start Screen stored?

Shortcuts to Modern apps

A little hacking around (and re-enforced by this article) led me to the following:

All Modern UI Programs are stored in the same place: C:\Program Files\WindowsApps\ (found out by doing an open file location from the task manager on a Modern UI app).

Since it all Modern UI apps are stored there, there is nothing that prevents windows from simply assuming that everything in that folder is in fact a modern UI application, and follows that convention.

The article I linked to above seems to support this conclusion.

In short, there are no shortcuts to Modern UI apps, it just enumerates the contents inside C:\Program Files\WindowsApps\

Shortcuts to Non-Modern apps

As I don't use Windows 8, I couldn't answer the question, but I did specify how to easily find that out :

Open the Start screen, right-click a non-metro tile and choose Open file location at the bottom of the screen. This opens an Explorer window to the location of the shortcut file.

The result for Gam Erix was that the location is at :
C:\Users\<username>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs.

The result for All Users, as pointed out by @mtone, is :
C:\ProgramData\Microsoft\Windows\Start Menu.

These folders are exactly the same as they were for the Windows 7 Start Menu.