xdg-open basically just looks to see which desktop environment you have and then runs gnome-open, gvfs-open, xfce-open, etc. See below for desktop environment specific instructions...

Gnome

Gnome uses the gnome-open program which uses gconf to store everything. For example on my machine with Ubuntu 10.10 running gnome-open irc://blah opens up xchat because xchat includes a gconf setting patch to add an irc:// handler.

This shows how gnome does this, with a gconf settings in /desktop/gnome/url-handlers/. See xchat-2.8.8/src/common/dbus/apps_xchat_url_handler.schemas as an example.

KDE

For KDE you should look at the .protocol files in /usr/share/kde4/services/, create a new one for your new protocol and put it in ~/.kde/share/kde4/services/, if it's super useful then consider adding it to the package as a fix for other users.

KDE is using kde-open or kfmclient depending on what's available and what version of KDE you have.

XFCE

XFCE uses a program called exo-open, this program doesn't have any way to configure it or add uri handlers. Looking through the source code shows that is uses desktop files to specify only three types of programs. TerminalEmulator, WebBrowser and EmailClient.

With XFCE4 (and probably also others) it is possible to configure xdg-open to define a custom protocol handler. In some you have to create/edit the following files:

~/.local/share/applications/protocolhandler.desktop
~/.local/share/applications/mimeapps.list

An example adding a handler for the ed2k protocol is provided at stackexchange.com2.