As any new user to ubuntu will notice, not every package they install on their system through the Package Manager will show up in the Applications menu.
Gnome and KDE use a recent standard, developed inside the freedesktop.org's project, for a common menu format, which means that application developers only have to add a few lines of text to their application, and it will be automatically shown in both desktops. XFCE also uses this standard.
The bad news is, that this standard is so recent, most of the applications available in the Ubuntu repositories still aren't packaged with this information.
The good news is that Debian has had their own menu system up and running for years, with every package in their repositories adding themselves to the Debian menu.
The excelent news is that you can install this Debian menu in Ubuntu and make use of it!
1. Launch the Package Manager (Synaptic)
2. Go to Settings->Repositories
3. Activate the Universe repository
4. Search for and install the package named "menu"
5. Run in the Console:
Look in your Applications menu, and you will have a new menu called Debian with all the applications you installed using synaptic, apt-get or individual .deb packages. Aditional applications you install using these methods will be placed there, as the update-menu is automatically run when a package is found to be using the debian menu.
For Kubuntu, the instructions are the same, and the Debian menu will be placed in the "K" menu.
Other desktop environments should (or could?) use Debian menu, but if they don't (XFCE aparently doesn't), there's still use in it.
1. Install pdmenu
2. From a console, run
which will give the Debian menu in ncurses.
After you've installed "menu", you'll have full documentation of it in your system in this directory:
The manual is in: