First, figure out what keymap you're currently using. Try going to /etc and do a recursive grep for "loadkeys", which is the program that actually sets the keymap. Now read that file to figure out where and how the keymap is chosen.
Next, find a keymap that's close to what you want to use (probably the one you're already using, perhaps us.kmap.gz if you're using Debian in the US and picked the defaults during install, us.map.gz on Fedora). Edit it. Suppose you want your Backspace key to send Backspace (control-H) rather than Delete (control-?). You want a line that looks like:
keycode 14 = BackSpaceso either change the existing keycode 14 line, or just add that.
Or suppose you want to make your caps lock key into another control key. Look for a line that says:
keycode 58 = Caps_Lockand change it to
keycode 58 = Control
Then save the file, either in place or to another name such as yourname.kmap.gz. If you renamed it, now persuade your OS to use that keymap (in Debian, this is done by changing CONFFILEROOT in /etc/init.d/keymap.sh; in Fedora, try /etc/sysconfig/keyboard). You may need to save it in multiple places: in Debian, you'll probably want to save a copy in both /etc/console and /usr/share/keymaps/i386/qwerty, because the keymap is set twice during the boot process (why? shrug). In Redhat, they seem to live in /lib/kbd/keymaps/i386/qwerty. On other distros, "locate qwertz" will get you started finding the keyboard map directories.
Test it before rebooting: loadkeys filename.gz then bang away on the keyboard (try it both in a console and in X) to see if it worked. That should take care of the console.
Under Redhat (including Fedora), X overrides the console keymap somehow. I haven't figured out how -- the /etc/X11 setup in FC3 is immensely complicated and seems to include all current and obsolete settings for every possible platform under both X.org and XFree86. Options include xmodmap, or doing some sort of mapping with the X Keyboard Extension.