Getting Bluetooth headsets working is not trivial. Doing it before Lenny is hard.

Here is what to do on Lenny-vintage Debian or Emdebian

Requirements

useful info at http://wiki.bluez.org/wiki/HOWTO/AudioDevices

also for testing:

initial config

hcitool scan to get mac:
  00:0F:DE:0A:B5:23   HBH-300

edit ~/.asoundrc to have 

pcm.bluetooth {
  type bluetooth
  device <mac>
}

You need to pair device (see below for discussion - it's difficult from console - easy from desktop).

playing

playing the stream from the headset: 

mplayer -ao alsa:device=bluetooth <file>

recording

to record: 

arecord -D bluetooth -f S16_LE <filename>

to playback: 

aplay -f S16_LE <filename>

Pairing

To pair either install bluez-gnome and type into window it pops up, or edit /etc/blueooth/hcid.conf to change passkey to 0000, then restart hcid 

/etc/init.d/bluetooth restart

(or somesuch - I failed to get this to work, but I know Bala has in the past)

Simplest solution for command-line world is to compile passkey-agent (in /usr/share/bluez-utils/examples (in Debian - stripped from emdebian package)) and use that (command-line equivalent of the gnome-passkey thing) 

apt-get buildessential libdbus-1-dev
cd /usr/share/bluez-utils/examples
make

Then run it with 

passkey-agent 0000

and finally it's possible to add a line to /var/lib/bluetooth/<deviceMAC>/pincode of the form 

<MAC address><whitespace><pincode>

(See /usr/share/doc/bluez-utils/README.Debian.gz)

If it's not paired the error from the mplayer line below is: [AO_ALSA] alsa-lib: pcm_bluetooth.c:1593:(bluetooth_init) BT_GETCAPABILITIES failed : Input/output error(5) [AO_ALSA] Playback open error: Input/output error Could not open/initialize audio device -> no sound.

If you have a desktop then by far the easiest way is to install bluez-gnome and run bluetooth-applet, then when you run the mplayer line or asound line it pops up a window asking you to enter passkey.

To run bluetooth-applet without the whole gnome insfrastructure you need to install hal and dbus-x11 

apt-get install hal dbus-x11
DISPLAY=:0 bluetooth-applet

(which is about another 9MB)