First, make sure you have the Developers Tools installed. Start the application "Interface Builder" located in /Developer/Applications.
Right click on the application you wish to modify and select "Show Package Contents." Navigate to Contents -> Resources -> English.lproj. You may wish to make a backup of the application first, just in case...
Drag the file "MainMenu.nib" to the Interface Builder icon on the dock to open it. You will see the menu bar of your application presented for editing. Just double-click on the various elements to change them. You can double-click on the hotkey letter to change it to something else. Save it and restart your application to enjoy the new shortcuts.

