* To enable menu editing per user config (via nautilus), you need to open a terminal and do the following:
su -
<give root password>
cd /etc/gnome-vfs-2.0/modules
cp default-modules.conf default-modules.conf-no-menu-editing
cp default-modules.conf.with-menu-editing default-modules.conf
For any user you want to have the right to edit their menu, you also need to do this as the user:
cd ~/.gnome2/vfolders
cp /etc/X11/desktop-menus/applications.menu applications.vfolder-info
* When gnome-panel is restarted (via logout/login or kill) the user will be able to see the changes they have made to their menu.
* As some have noted, the above is a slightly risky way of menu-editing. It could break your menu in some cases. There is however a great resource which explains how the menu system works, and from this you should be able to customise your menu easily enough. Checkout bluethingy.com for more info. Here's google's cache if the site times out (it did for me).