I'm not sure how to do it with Gnome, I use KDE myself, but the process might be similar:
- Right Click in your desktop, then choose "create new" >> "link to program"
There you are able to create a name to your shortcurt as well change the icon. In the tab where it reads: "Run", you can specify where the program that you desires to run, to run
Remember, you can as well type only the bash syntaxes there instead of navigate all throug your folders. EG:
if in the console you can type "licq" or "xine" to run those applications, the same can be used in the tab "run" of your application. One last tip, some programs needs to run as a root. If you want, you can set your new shortcut to do so. EG:
right click >> create >> link till program. In the "Run" tab, type licq and down this same run tab, note "Run program as another user", there, you can type root.
Hope you could understand my english sallad