With Pyrrha you can now record music from the streaming radio stations that you set up in Pandora.

Update:
You can still find the application here. (Thanks, Trevor)

The application gives you a simple interface where you log on to Pandora, select the channel you want to record and how long you want to record.

Pyrrha makes one 128 kbit MP3 of the recording and a playlist-file (PLS) with the correct song and artist names. Simple as that.

Have fun while it last.

Pyrrha used to have a page on their site with an explanation of the fact that it is legal to record your Pandora radio stations for personal use. For some reason this page has been removed. When I tried Pyrrha for the first time it was a trial, and Pyrrha had a page where you could purchase the full version.

Right now the information on the Pyrrha site is very limited and for me it seems like the version 1.0.1 of their application is a fully working free version.

Update:
I got this very good answer from Pyrrha:

Unfortunately after pursuing legal council it came to our attention that we could incur legal liability if we charged for this type of application. In light of this information we have decided to release the application for free to the community to enjoy. As a part of this release we also hope to obtain feedback from the Pandora.com user community with their reactions and thoughts on the legality and usefulness of such an application. If the community deems this type of application valuable we would encourage the community to email Pandora.com with their thoughts.

Additionally we are attempting to provide small improvements to the current application and will take into account your suggestions in regard to duration control and login credential saving. We are also looking for feedback from the community and would love submissions for feature enhancements. I must preface this however by the fact the we have chosen to not support the download of single mp3 files and consider this an abuse of the Pandora.com service.

We ultimately hope that our application will bring additional attention to the Pandora.com service and the experience it can provide users outside of the web browser. We will also attempt to reintroduce a legal disclaimer about the use of Pyrrha. One point to note is that we are attempting to distance ourselves from the moniker “podcast” because this could convey the distribution of copyright materials from the Pandora.com service which we obviously discourage.