I was over on videos4blackberry.info (which I also highly recommend) and on his home page he had an announcement about Slacker.com being available for Blackberry. I downloaded it and have been playing with it for about 1/2 hour and it appears to rock!
You can stream music on your BB on already created radio stations and create your own. On top of that, you can pick any radio station and "cache" it - when you plug in your BB via USB, it will download the content from the station(s) you choose to your memory card which you can play later when you don't have connectivity (like on a plane).
You can do an OTA download by going to slacker.com on your BB browser.