I've been using CG-WhatTunes (part of the CG-PowerPack: http://www.chait.net/index.php?p=238 ) for quite a while now. It's very nice.
Basically, it provides a URL that you "ping" with the song title, artist name, album, etc. This causes it to add that song info to a list of songs. Then you can display the latest song added, the last N songs, etc. It also integrates with the CG-Amazon plugin to retrieve album art and create links to Amazon for people to buy that album and such.
This sort of URL "ping" is supported by many different programs and is the more or less defacto approach for now playing type blog plugins. Some players have built in support for it, like musikCube has a function called "Tunage" which can do this. If you use iTunes, there's a program called "iTunesBlogger" which does the same thing and pings a URL when it sees that your track has changed. Winamp has several different plugins that can do this, and there's some for Windows Media Player as well.
You can look at the right hand side of my (currently rather "busy") blog to see an example of the plugin in action. It shows the latest song I played along with the previous 5 songs below that. All of them link to Amazon.