Music on Rhapsody is supplied in two formats - MP3 and WMA.
When you buy individual songs on Rhapsody such as to play on any MP3 player, they are provided in the MP3 format, which any MP3 player can play, including the iPod. These songs don't have any copy protection measures and thus can be played on any equipment capable of playing MP3 files.
However, when you download songs as part of the Rhapsody subscription, they are provided in the secure WMA format, which is totally incompatible with MP3. These WMA tracks are protected with DRM, which means that they are encrypted and will only play back on players capable of playing of handling WMA with authorisation support for DRM. Besides copy protection, the DRM ensures that the music will only play if you have an active subscription. Unfortunately, while most MP3 players support WMA, not many support DRM protected WMA tracks.
While there is third party firmware available for the older iPod generations to play other audio formats, they do not provide DRM support. Also, as far as I'm aware of, there is not any third party firmware compatible with the the latest generations of iPods (e.g. iPod Classic, Touch, 2nd+ gen Nano, etc.)
There is a wide range of software tools available to convert DRM-protected music to play on the iPod, which all rely on either removing the DRM or creating MP3 versions of the protected songs. This webpage gives a nice list of conversion utilties, with a few freeware ones towards the bottom of the page.