I ran across an interesting problem recently, all the icons on the desktop were missing! The first thing I looked at was the desktop folder to make sure there where actually icons there, and they were there. The desktop folder can be found under: My Computer >> Local Disk C (default location) >> Users (Documents and Settings under Windows XP) >> [User Name] >> Desktop. The desktop folder contains all the files, folders, and shortcuts on your desktop. Some of the shared shortcuts, including links to My Computer and Network shortcuts will not be in the folder.
Now there are quite a number of things that can cause desktop icons to disappear, the most common that I have seen are Viruses and accidental deletion. In this case there was no virus and the icons were in the desktop folder so they were not deleted.
The problem in this case was that the Show Desktop Icons was unchecked! To access this option, you need to right click on an empty space on the desktop, go to View and Show Desktop Icons (not sure why you would even want an option like this? except for maybe a Halloween prank!).
If you have a problem with your icons disappearing after a virus then I suggest trying this program: http://download.bleepingcomputer.com/grinler/unhide.exe