Where's the source for the other labels doing a deal? The source you linked only talks about EMI, and a cursory glance around the web doesn't find anything to corroborate other labels doing any deals.
As far as I understand, basically the same way YouTube and
Vimeo are: DMCA safe harbor laws, plus paying streaming
royalty boards etc. We're also trying to get direct deals
with all the majors too, but those negotiations take a looong
time. It was a couple years just to get EMI signed.
So it looks like they only have an EMI deal right now but other labels are in progress.
I'm glad to see such a good service finally start to get all the recognition it deserves. I switched to grooveshark from pandora about a year ago and have not looked back. By far the best music service available.