How can they offer so many songs to listen to for free? Don't they have to pay licensing fees if someone listens to a song?
Songs are uploaded by users and much like YouTube, they only distribute professional songs when they've done specific deals (such as with EMI, as Pipermac said). Grooveshark itself isn't illegal, but many songs on there are distributed illegally.
Operating in similar fashion to other online services like YouTube and Vimeo, Grooveshark does not indemnify their users for any unlicensed uploaded content. Users have complained about the lack of indemnification protection found in their EULA. Despite these concerns, no user to date has faced legal action from Grooveshark or third-parties. Parties in the USA claiming copyright infringement may use mechanisms of the Digital Millennium Copyright Act (DMCA) to request that their content be removed.