Music Streaming: How do we stream music legally?

My friends and i came up with an idea that involves streaming music for free and paid members like spotify. We are aware that we will need to get licensed by record labels. We do not know how to go about it. These are our questions:

1. Do we send a proposal to them via email or mail?
2. Are we going to pay them to get the licenses(we intend to pay them royalty fees)?

Thanks

For streaming music you generally fall under the "radio broadcaster" set of requirements. This grants you a statutory license to play any music at a fixed royalty rate. All you need to do is track what you play. Royalties can be submitted to SoundExchange. In addition, your music streams must conform to RIAA guidelines. Microsoft has a pretty good writeup here.