(stripped from a tutorial I wrote on my website)
First, pop a terminal and become root. Go to /usr/share/applications. Create a file ending in .desktop and being somewhat descriptive of the program. For this example, lets create a menu entry for Al's MSN Messenger, a nice little app that looks and feels just like the windows version of MSN Messenger. I looked at some of the other files, and followed their naming convention. I called my new file net-amsn.desktop. Let's get into the guts of what goes in there.
Name=MSN Messenger <-- Name for the menu entry.
Comment=MSN Messenger <-- The tooltip text.
Exec=/home/username/msn/amsn <-- path to the executable file
Icon=/home/username/msn/icons/48x48/amsn.png <-- path to it's icon file
Terminal=false <-- run from a terminal?
That should suffice with the explanations, almost. One line to pay close attention to is the Categories line.
"Application" tells the system that this goes in the programs menu. "Network" puts it into the Internet sub-menu. "X-Red-Hat-Base" puts it directly under the Internet menu. If you leave out X-Red-Hat-Base, it will go into the "More Internet Apps" submenu. I personally don't like to have a second group for "non redHat apps" in my menu.
That's it. Save the file, then click on your menu. Notice your new entry. Now look at some of the other files and have fun.
I'm sure there are other ways of doing it though.