Replay Music (Windows) records from your sound card, so it can record from any radio station or online music service. Please note that it can't split songs when they are overlapped. However since in most cases there is a pause between songs, the program works just fine.

Replay Music is compatible with Windows. But you can use it in Linux with WINE as well:
How to install and run Replay Music in Linux (like Ubuntu 9.10)

If you don't want to record from your sound card, you can use audio stream rippers and streaming video recorders. Such programs work with limited number of formats and protocols only, but don't lose any quality while recording.