What? Are you being intentionally ridiculous. They license songs. I don't know the terms of these specific licenses but the way they work in general is that they can license the game for a specific use and/or term. I'm not a lawyer so I don't know specific legal terms off the top of my head but there's a different license for the PlayStation version of the game where they are giving the user a copy of the song to have and to hold and one where they would stream, which I assume the iOS version is actually doing. Again, not a lawyer so I don't know the specifics but you will often see something like a TV show having broadcast rights to use a song in their show but they (especially for older shows) may have failed to procure the appropriate rights to use the song on the DVD version.
Now, I don't know too much about the Rock Band app so I'm sure someone more knowledgeable about it is likely to come through and correct me but it sounds like the songs are streamed for the iPhone. This wouldn't be as crazy as it sounds since phones still have relatively limited space and applications with smaller footprints are thus easier to manage.