The cloud is an option, but how much storage would google give us? Is it already available?
I just got mine all set up just for the reasons everyone is talking about. I have 16gb of music with a 32gb sdcard in my Bionic (for 48gb total) and was worried that a 32gb phone (with no expansion capability) would be a problem.
Just go to google.music.com and you have to ask for an invite. Mine took about two days. Create your account, upload your music, get the app on your phone and you are up and running.
As far as storage, it's actually amazing what they are giving you. I looked at Amazon and a few others, but Amazon had the most for free at 5gb, which would mean I'd have to pay an annual fee for the extra. Google gives you 20,000 songs (with not nary a mention of how much actual space you get). My 16gb of music is about 2,500 songs, so I'm guessing they are giving me 124gb give or take.
And it looks like it's a great service. The app starts right up and playing (no delay), you can shuffle and browse, play by artist, song, genre, etc. You have to install a client on a pc to do the uploading, but then you can listen on the pc as well (only one at a time though).
But yes, you'd better have unlimited data for the service to be cost effective. As far as continuous connection, you can select artists, albums, songs, etc, to be cached for offline listening (or your entire collection I guess). So a continuous connection is not necessary.
All in all, pretty sweet, and alleviates my concerns about 32gb not being enough storage.