For Microsoft's Virtual PC - XP Mode follow these steps:
First verify "Automatically publish virtual applications" in enabled
1) Select "Windows Virtual PC" from the Start Menu to open a Windows Explorer window to the Virtual Machines Folder
2) Right-click on "Windows XP Mode" and select SETTINGS
3) Verify or Set "Auto Publish" to Enabled
4) Restart XP Mode if you had to Enable it (See 2C below).
Inside XP Mode
1) Create a shortcut to the program under the All Users Start Menu "%ALLUSERSPROFILE%\Start Menu\Programs\"

NOTE: It must be in ALL USERS not just the XPMUser Start Menu
2) Certain programs like IE6 and Internet Hearts/Spades are blocked from publishing. (thank you FlowMaN)
_a) Navigate to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Virtual Machine\VPCVAppExcludeList registry key
_b) find the names of the programs you want to publish and delete the entries.
_c) Restart your virtual machine. (Ctrl-Alt-Del and select "restart")

NOTE: This step is critical, just logging off or clicking the X to close (hibernate) does not complete the process!