I recently started using last.fm, which if you didn't know is a service that records the songs you listen to, provides statistics and recommendations, finds others with the same music taste, and allows you to sample music and music videos from related artists. I also just switched to Amarok from Rhythmbox because it seemed much more featureful.
Amarok is a great piece of software, although it takes a little getting used to. Here's a screenshot:
Last.fm is quite nice as well. Here's my music profile, which shows tracks I've recently listened to, as well as top artists and that sort of thing.
How the two integrate is pretty neat. When you play a song in Amarok, it gets "scrobbled" (to use last.fm terminology)—that is, sent to last.fm and added to your music profile. Here's how Amarok lets you reap the benefit of sending last.fm your data: Amarok has "dynamic playlists" that provide an automatic playlist of songs based on some criteron, like random selection or most-played tracks. But one setting allows you to put a few songs on your playlist and then enable the "Suggested Songs" dynamic playlist (it's enabled in the screenshot above). This allows Amarok to ask last.fm for suggested songs based on the current playlist and your account information. So you can leave it running and not have to keep refilling the queue with manually selected songs.
For more thorough documentation of Amarok, see the Amarok Handbook at docs.kde.org.
Note that Amarok is not associated with last.fm in any way except that it provides an open-source implementation of its client. It is the default player included with KDE.