Through the entire Republican era only Imperium-holding Magistrates of the Roman People were able to lawfully raise an army of citiziens. (a legion)
Private individuals could also form fighting forces from their slaves, clients or hired gladiators. That was sort of borderline, but happened quite often in the civil-strife ridden decades of the late republic.
But to raise a legion (or a serious auxiliary force from some client state or ally) one needed imperium. So either he had to be elected as consul or praetor, appointed dictator, given proconsular/propraetorian province after the magistral year, or conferred some special command by the vote of the People. (like the maritime super-command Pompeius got against the pirates)
So to get a legion, one should usually win some election, and then be properly inaugurated into command under the right rituals. There were some other restrictions, like one had to be of required age to be eligible to election, and after the proper election, one theoretically needed lex curiata de imperio too, but these could usually be bypassed by willpower and political support.
Under normal circumstances and dutiful conduct even magistrates would only conscript legions after consulting the Senate and reciving the decree of the Fathers that this is necessary for the public good, but proconsuls sent to remote and barbarian provinces could act more or less on their own discretion, even more so after they seriously started to pursue ambitions of power: look at the case of Caesar, he happily levied two legions in Cisalpine Gaul when he perceived/claimed that war threatened in his province (book 1, section 10, CdBG) and later could freely demand horsed auxiliaries from the newly conquered peoples.
EDIT: On appointing promagistrates:
Under ancient custom and religious taboo only the consuls (and dictators in special case) possessed the full ius auspicium - the power to consult the gods on questions of war - and they were the only ones authorized to lead a whole army against the enemies of the Roman People.
When in 327 Publilius Philo's consular year terminated while an important siege was underway, the romans turned to legal fiction: The Senate decreed that he could retain his command, acting 'pro consules' - that is, in place of the consuls.
As Rome obtained overseas territories and organized provinces, need arised for authorized commanders at every frontier. (while actual praetors and consuls had quite enough work in Italy) The exception became norm.
By the time of Caesar it was expected and almost self-evident that the major magistrates would each get one province to govern after their magistarial year was over.
Often they drew lots to distribute the governorships, although smaller and non-frontier provinces like Sicily would usually go to propraetors. On occassions the vote of the Senate had a say in the distribution, and the duration could vary: one year was normal but powerful and aggressive politicians could get five.
So in fact promagistrates were never properly integrated into the roman constitution (of course there was no such text, only customs and best practices inherited from the ancestors), and some say (like Machiavelli) that this contributed greatly to the fall of the Republic.