Using GNOME/Application menus
The process for editing the applications menu in GNOME is unintuitive. Open the Nautilus File Browser, and enter applications-all-users:/// into the location bar, loading up what is effectively a folder filled with Launchers, or shortcuts, which you can edit or add to, to change the layout and contents of your application menus.
In some versions of Gnome this does not work without using third-party software. To work around this you can edit menus manually, by going to /usr/share/applications/ in the file browser. This will be filled with launchers too which you can edit or add to. The downside is that, for them to appear in the Application menu at all, you must assign them to certain categories and this can only be done by editing the launcher files using a text editor.
The categories that Launchers can belong to in the menus are often easy enough to grasp, i.e. they might be the names of the sub-menus in the Application menu, and by assigning them to these categories, the Launcher will appear in respective sub-menus in the Application menu. However the category names are not always obvious, so you might have to have a look at the contents of existing Launchers to tell for certain.
Launchers, or .desktop files are essentially text files which contain data, i.e. for the location of the icon to use, the command to run or folder to open when the launcher is used, etc. You can open these Launchers in text editors like Gnome's. Here is an example of a Launcher, when opened in a text editor:
[Desktop Entry] Version=1.0 Encoding=UTF-8 Name=Mozilla Firefox Comment=Mozilla Firefox Web Browser Exec=/usr/bin/firefox %U Icon=firefox-icon.png Terminal=false Type=Application Categories=Application;Network; GenericName=
This is a Launcher which starts Mozilla Firefox. As you can see, there are properties there, such as name, comment, etc. which determine the appearance and behaviour of the Launcher. When working with Launchers in Gnome, you can modify almost all of the important values just by right-clicking on the Launcher icon and selecting its properties. When you modify the Application menu from /usr/share/applications/, this is what you should do. However, one important property, Categories, you cannot modify using the Properties dialog, and so must modify in the text editor.
To assign a Launcher to a particular category, first find out exactly what the category is called, by opening up a Launcher that is already in the category. For instance if you were adding something to the Internet sub-menu in the Applications menu, you could open up the Firefox Launcher and observe that the category is called Network. Also observe the entry under Categories called Application. This is included as a convention also, as it might influence the behaviour of other versions of Gnome. Into your new Launcher then you would enter the line:
Categories=Applications;Network;
This line can go at the end of the text in the Launcher, or if there is already a Category field, you should replace the existing one with the new one. To enter a Launcher into a different category, obviously you would use different values for the Category field. Also note that if you wanted an application Launcher to appear under multiple sub-menus or Categories at once, you can simply add the other category at the end of the values you have already, remembering to separate them with semi-colons. So if you want to add this particular application to Network and Graphics, you would add to the end of the existing value, Graphics; so that the line would appear as so:
Categories=Applications;Network;Graphics;