As mentioned above, there are a few different package manager in use. You should at least support .deb, .rpm to target the most widely used distros (i.e. Ubuntu and Fedora). You can also provides packages for archlinux based distributions through the AUR.
For debian packages, I recommend using a PPA. There might be an equivalent service for building and distributing rpm but I personally don't know any (I am an arch linux user)
What about adding entries to their application launcher of choice (ie kickstart menu on KDE or whatever)?
You do that with desktop entries: http://standards.freedesktop.org/desktop-entry-spec/desktop-entry-spec-latest.html. This will work regardless of the desktop environment.