Tried  last.fm for the first time. shell-fm[1] feels like a reasonable
  client.

  I'd love to keep using MPD[2], though. I don't quite know yet how  one
  is  supposed  to  use last.fm with MPD. All I can do is add a bunch of
  songs to my playlist but that's it. How do I do continuous playback?

  Well, last.fm-support in MPD is in a pretty early  stage  anyway.  One
  has to use mpdscribble[3] or another client to "scribble" songs...

  ____________________

  1. http://nex.scrapping.cc/shell-fm/

  2. http://mpd.wikia.com/wiki/Music_Player_Daemon_Wiki

  3. http://mpd.wikia.com/wiki/Client:Mpdscribble