A Lable is just a name. To start a label, you make up the name. Pada! Done!
Now, if you also are intending to sell records on the label, you would be best adviced to start a company. And when you are selling stuff, you can't use anybopdy elses nice name, so you need make sure you aren't. This is done by registering the label name as a trademark.
You can also use the company name as label name (maybe you even have to in your country, but I doubt it) but the problem with that is that if the company goes buts, the label name goes with it.
So register the trademark separately.
Also, if you are serious, create two companies. Let one company hold all the assets, and let the other company take all economic risk. That way you don't risk the assets.