Create a application link, and, as the application, use sh ~/.../myprogran, or, if you're using KDE, try konsole -e ~/.../myprogram as the application. (Where, of course, ~/.../mprogram is the path to your program.)
By the way, the "konsole -e" is an easy way to run shell scripts from desktop icons. That can be quite handy at times.
(Um, for GNOMEies, is there a similar method available in GNOME?)