from what i have learned so far, it matters with the program. the best way, for us noobs is to just delete the short cut. with some things, if you did a make install, you can do a make uninstall. or if you look where the program was stored somtimes, there is a uninstall binary. otherwise, if it is a really really big program, just delet the big files and the shortcut and hope nothing goes wrong.
however, if the program was an rpm, you can do it easily: rpm -e (programname)
same with .deb too but i haven't used those before.
also, if you use synaptic, everything is easy.