I have Mac OS 10.8.5 and I'm not sure what I was doing but all of a sudden I have an icon on my Desktop for All My Files. Where is this icon supposed to be?
It sounds like you accidentally dragged All My Files from the top of the Finder (screenshot below) onto the Desktop. You can just drag it to the trash.
If you select it then do command-i you should see that it is just a saved search. I dragged it straight from the top of Finder to the desktop to test before my earlier post to you and it did create the desktop link.
That is normal. Just go ahead and delete it. I just did another test and the Desktop link I made was 1.7MB. It looks like it varies in size depending on the saved search results.