The short answer for third party applications is:
Install desktop entries to
datadir/applications/ for each menu
item. Please namespace the filename, as in "vendor-foo.desktop", or
use a subdirectory of
datadir/applications/ so you have
"vendor/foo.desktop." Please be sure all desktop entries are valid
(see the
desktop-file-utils package for a validation utility).
Install an XML menu file to sysconfdir/desktop/menus/applications-merged/ to add any submenus, if your desktop entries aren't already
included in some common categories.
Install any directory entries needed for your submenus to datadir/desktop-directories/, taking care to namespace and validate
the directory entries.
Also, at least for a good long while, installing a directory hierarchy to the old GNOME/KDE specific locations such as /usr/share/applnk and /usr/share/gnome/apps should work. There are two ways to support both the old and new menu systems at the same time:
If you add a Categories line to the desktop
entries in the legacy hierarchy, implementations of this
specification will ignore their location in the legacy hierarchy,
and arrange them according to Categories instead.
This allows you to install a single desktop file that works in all
cases, though on the down side it's in a legacy location.
If you add the line OnlyShowIn=Old; to a desktop
entry, then old legacy implementations that ignore
OnlyShowIn will still show the desktop entry, but
implementations of this specification will not. Thus you can
add an "OnlyShowIn=Old;" entry to the legacy
hierarchy, and a new-style desktop entry to
datadir/applications/, and still get
only one entry in the menus.