Depende del "desktop" que ocupes. Aquí (Red Hat 9), usando KDE, basta con:
1. Click derecho en el escritorio
2. Nuevo -> Enlace a aplicación
3. En "General", poner nombre e ícono.
4. En "Ejecutar", poner el ejecutable del programa (por lo general es lo mismo que el nombre, pero en minúsculas).
5. Listo!!!
Para saber cuál es el ejecutable del programa, eso también depende de qué distribución de Linux uses. Por ejemplo, en Red Hat basta con ejecutar
Código:
rpm -ql nombredelprograma | grep bin
y con eso obtienes el nombre de los archivos ejecutables del programa.