Depends on the distro that you are using.
With Mandrake, using KDE, its very simple. Just create the menu item for the relevant program and then drag it to the desktop.
I've not tried this in other GUIs, but I suppose there should be a similar procedure.
I'll try it out in GNOME today and tell you.