Adapted from [1]; one disadvantage with the above is that it adds the song to the playlist, rather than playing an already-existing song. This would be undesirable for users who have one playlist of all their music.

#!/bin/bash  
mpc play `mpc playlist | dmenu -b -nb "#000" -nf "#7af" -sb "#000" -sf "#bdf" -p "Find:" | cut -d')' -f1`

You'll need to save this as some_file and then chmod +x some_file, then bind it to a key; keybindings vary by wm/de. It is probably not as fast as it could be, but it works nonetheless.

UPDATE (november 27, 2009) :
Since ba8daca21a8d2beb8e4267015da5fce42c6aaed0, mpc no more prints the song number, the following workaround it :

mpc play $(sed -n "s@^ *\([0-9]\+\);$(mpc playlist|dmenu -i -p 'song name'||echo ";;;")@\1@p" < <(mpc playlist|nl -s ';'))

Another newer script was written by Scj:Edit

1) make sure you have a patched dmenu with the vertical hack

(can be dowloaded from [2])

2) install gawk and socat

In ubuntu issue:

apt-get install gawk socate

3) paste the following script in the demnu script you want to run (and bind to a key):

#!/bin/bash

dmenu_opts="-xs -b -i -l 15"

mpd()   { socat - tcp-connect:localhost:6600 ; } 
query() { echo $* | mpd ; }
get()   { grep "^$1:" | sed 's|^'$1': \(.*\)|\1|' ; }

pick(){
  case "$(echo -e "album\ntrack" | dmenu $dmenu_opts -p "pick what?")" in
    "album")  query list filename album "\"$(query list album | get Album | dmenu $dmenu_opts -p "pick album")"\" | get file ;;
    "track")  query listall | get file | dmenu $dmenu_opts -p "select song" ;;
    *) exit 1;;
  esac
}

add()     { gawk 'BEGIN {print "command_list_begin"}      {printf "addid \"%s\"\n", $0}             END {print "command_list_end"}' ; }
queue()   { gawk 'BEGIN {i=0;print "command_list_begin"}  /Id:/ {i--;printf "moveid %d %d\n",$2,i}  END {print "command_list_end"}' ; }

pick | add | mpd | queue | mpd

# vim:set ts=2 sw=2 et:

muss is a simple and fast music player interface built with dmenuEdit

• creates a new playlist with ALL matching items from dmenu (requires small patch to dmenu 4.1.1)
• can work entirely from command line (without dmenu at all) to search collection for matches with keywords

for documentation and code, see http://github.com/dbro/muss