Isso depende de cada programa. Tem certeza que é SEMPRE que instala uma aplicação?
Geralmente as aplicações instaladas pelo Synapitc criam um atalho no Menu, já as instaladas de forma independente não criam. Alguns só reiniciando do Gnome pra aparecer.