Unfortunately Gnome doesn't provide a simple and well documented way to add/modify a menu entry, however Alacarte is a great tool for that.
On Fedora (Alacarte is also available in many distro) :
natjohan# yum install alacarte
To get it works on Fedora (I just tested it on F17), you have to edit /lib/python2.7/site-packages/Alacarte/MenuEditor.py and replace applications.menu by applications-gnome.menu and save it before launch Alacarte
Now you can add/modify/delete your menu entries with Alacarte (start it with Activities -> Applications or with Alt+f2 -> Alacarte)
Note : You can change icon by clicking on the little picture on the left