I want to be able to distribute a program in Linux without distributing the source with it. The current solution is distributing a tar.gz with a precompiled binary. What is the easiest way to have this binary be placed in the Applications Menu? Is there a way to do this that is common across most linux distributions, but Ubuntu, Fedora, and OpenSUSE would be the priority.
You will want to create a .deb and a .rpm. The former covers Ubuntu (Debian variants), and the latter Red Hat variants. You can also supply a standalone executable for other users who can deal with things like menus themselves.
You will have to deal with Gnome and KDE menu management, and also different distributions lay out their menus differently. There is also the issue of netbook variants such as Moblin, that have a netbook interface that probably has its own "add application" mechanism. I don't know if it is possible for a single .deb to handle both Gnome and KDE menus systems (for Ubuntu and Kubuntu respectively) but I imagine the capability is there to reduce duplication of effort for Ubuntu.