There are more than one ways to set Keyboard Shortcuts in GNOME. In my Ubuntu 7.04, you can either go to System -> Keyboard Shortucts and change/add keybndings there. This way, you can change keybindings for most common operations like "Launch Web Browser" etc.
There's another way, a very versatile one, provided by GTK. In almost any GTK application, you can give shortcuts to menu items. Just open the menu, and point with your mouse on the menu item you want to give a shortcut to, and press the shortcut key. GNOME will automatically assign that shortcut to that menu item, and remember it.
If the procedure outlined above doesn't work for you for some reason, launch gconf-editor from a terminal. Make sure that desktop/gnome/interface/can_change_accels is true. Happy shortcuts!