It seems that the Romans initially allowed the Jewish authorities to exercise capital punishment, but withdrew the privilege some time during Jesus' life.
The historian Josephus writes of an instance in which stonings occurred, probably around the year 62 CE. The short version is as follows:
The Roman prefect of Judæa, a man named Porcius Festus, died in office. This being the Ancient Roman Empire, it took a while for word of the death to reach the capital, and an equal amount of time for the new prefect, whose name was Albinus, to arrive in the region. The high priest at the time was Ananus, or Hanan. He had had problems with a few people in Jerusalem, including Jesus' brother, James. Josephus tells us that Ananus now exploited the temporary power vacuum, and had the alleged troublemakers stoned to death. The people of Jerusalem were outraged by this abuse of power, and immediately complained to Albinus, before he had even reached Judæa.
Here is Josephus' account:
CONCERNING ALBINUS UNDER WHOSE PROCURATORSHIP JAMES WAS SLAIN; AS ALSO WHAT EDIFICES WERE BUILT BY AGRIPPA.
AND now Caesar, upon hearing the death of Festus, sent Albinus into Judea, as procurator. But the king deprived Joseph of the high priesthood, and bestowed the succession to that dignity on the son of Ananus, who was also himself called Ananus. Now the report goes that this eldest Ananus proved a most fortunate man; for he had five sons who had all performed the office of a high priest to God, and who had himself enjoyed that dignity a long time formerly, which had never happened to any other of our high priests. But this younger Ananus, who, as we have told you already, took the high priesthood, was a bold man in his temper, and very insolent; he was also of the sect of the Sadducees, who are very rigid in judging offenders, above all the rest of the Jews, as we have already observed; when, therefore, Ananus was of this disposition, he thought he had now a proper opportunity [to exercise his authority]. Festus was now dead, and Albinus was but upon the road; so he assembled the sanhedrin of judges, and brought before them the brother of Jesus, who was called Christ, whose name was James, and some others, and when he had formed an accusation against them as breakers of the law, he delivered them to be stoned: but as for those who seemed the most equitable of the citizens, and such as were the most uneasy at the breach of the laws, they disliked what was done; they also sent to the king [Agrippa], desiring him to send to Ananus that he should act so no more, for that what he had already done was not to be justified; nay, some of them went also to meet Albinus, as he was upon his journey from Alexandria, and informed him that it was not lawful for Ananus to assemble a sanhedrin without his consent. Whereupon Albinus complied with what they said, and wrote in anger to Ananus, and threatened that he would bring him to punishment for what he had done; on which king Agrippa took the high priesthood from him, when he had ruled but three months, and made Jesus, the son of Damneus, high priest.
- Flavius Josephus, Antiquities of the Jews, Book XX, Chapter 9 (Greek, English)
Josephus explicitly states that it was illegal for the high priest to assemble a Sanhedrin without the consent of the prefect. If we assume that a stoning could not take place without the permission of a Sanhedrin, and if no Sanhedrin could be held without the consent of the prefect, it would appear that stonings could not take place without the approval, direct or indirect, of the Roman authorities. This agrees with the account provided by Josephus: it is plainly the case that Ananus wasn't deposed simply because he stoned someone; he was deposed because he stoned someone without the imprimatur of the Roman prefect. This makes it fairly clear that, regardless of whether stoning was still officially condoned by the Jewish authorities, it was still legally possible, but only if the Roman prefect had already given his consent.
This idea is further supported by the historical evidence:
The right of exercising capital punishment autonomously, even over their own countrymen, was withdrawn from the Jews by the Romans in the first... century [of the Common Era]. The precise date is controversial, but the limits are clear. E. R. Goodenough notes that the Greeks in Cyrene were allowed by Augustus, in a decree of 6 B.C., full judicial rights in everything short of the death penalty - this was reserved to the Roman governor, according to the customary provincial administrative pattern. Many scholars therefore maintain, with widespread Roman precedent, that the Jews lost the right of inflicting capital punishment in A.D. 6, when Palestine became a Roman province. Others believe that Jewish courts were allowed exceptional privilege in this matter until the Jewish revolt was crushed and the Temple destroyed in A.D. 70.
The official Pentateuchal methods of capital punishment were stoning, burning and decapitation by the sword, these being enumer- ated in their descending order of severity. The Rabbis added a fourth and milder alternative, strangling. They may well have reasoned that this left the body unmutilated for resurrection. Paul Winter thinks that strangulation was a late device, used surreptitiously and illegally to get rid of Jewish apostates, undesirable or undesired, without Roman interference. The crimes for which each particular penalty was appropriate have been listed exhaustively. There seems no good reason to doubt either the intense dislike which the Rabbis felt towards death sentences under any circumstances, or their sincere desire to minimize the physical sufferings involved. Crucifixion is not normally added to the list of Jewish methods.
A man condemned to stoning was sometimes hurled over a precipice first, to abridge his sufferings. This was obviously the intention of the Nazarenes against Jesus in Luke 4: 29, whereas Stephen was judicially stoned on ground level in Acts 7. This certainly proves that such things happened under Roman rule by direct Jewish action - it neither proves not disproves their legality from a Roman viewpoint.
The stringency of the laws of evidence underlines the extreme reluctance of the Jews to impose death sentences, even when they possessed full civic rights. Circumstantial evidence was entirely discounted, for the Pentateuch insists on two witnesses (Numbers 35: 30; Deuteronomy 17: 16). An assassin might conceal his victim behind a wall, run a sword through his heart, and withdraw the blade-even if a crowd of people saw him five seconds later, while the blood dripped from the sword, he could not be charged with murder, for the actual deed was committed without witnesses-and these should have been at least dual. Persons giving evidence must be of full age and good character, not attached to any of the more profligate professions, not related to the accused, and without personal interest in the matters under litigation. The judge must elicit any contradictions in the evidence by severe cross-examination -the case of Susanna is famous. Any circumstantial contradiction destroyed a capital charge, though not necessarily a civil one. The principles of evidence are the same in all cases-where a human life is involved, the stringencies are tightened.
It would follow historical precedents if the Jews lost the ius gladii [literally, "the right of the sword", i.e., the legal right of a group of people to exercise capital punishment] in A.D. 6, when their land became a Roman province. Josephus describes the first Roman procurator Coponius as invested with the power of life and death by Caesar... But Josephus nowhere lays claim to any such Jewish authority in this period - indeed he blames the High Priest Ananus for overstepping his prerogatives by ordering on his own authority the stoning of James the brother of Jesus [and others].
The Jerusalem Talmud clearly states that Jews lost the power of capital punishment forty years before the destruction of the Herodian Temple, and the Babylonian Talmud echoes this1. Forty could be a round number, translatable into sixty-four. Newman believes that the Great Sanhedrin left the Hall of Hewn Stones in the Temple about A.D. 30, for reasons internal to Judaism, and that this fact, not Roman interference, caused the cessation of the death penalty. Roman practice does support the simple, factual understanding of John 18: 31: "We possess no civic power to impose a judicial death sentence at all." This was the interpretation of Schiirer, Mommsen, Bernard, Jeremias, Rosenblatt, and a host of other scholars.
Others insist that the Romans permitted [Jews] to exercise the death penalty, against Jews only and in matters exclusively religious, until A.D. 70. Jean Juster argues this with immense learning, scant respect for Gospel historicity, and a propensity to read into Josephus what suits him - that the High Priest's προστασία ["aegis", "auspices"] includes ius gladii is gratuitous assumption. T. A. Burkill reaches the same conclusion from the Temple inscription in Greek, warning Gentiles not to proceed beyond their court on pain of death2. Deissmann, however, attributes both inscription and penal procedure to Roman authority, which would invalidate Burkill's argument entirely.
Mediating theories attempt to retain Jewish capital competence, but explain John 18: 31 circumstantially. Suppose, exempli gratia, that the Jews could stone Jesus for blasphemy-they failed to establish their case, and therefore fabricated a political charge of sedition, which became Pilate's province. Hoskyns73 states that άποκτείνω [the Hebrew equivalent would be "מות", the causative form of "kill", which gives us a literal translation of "make die"] implies bloodshed, certain in crucifixion, but not in stoning. Ούκ εξεστιν ["not lawful"] then means that Passover bloodshed would render Jews levitically unclean. Note the scrupulosity of John 11: 55; 18: 28.
The fact that many Jews were, like Stephen, judicially killed by their compatriots in many parts of the Roman Empire between A.D. 6 and 70 is not disputed. Goodenough demonstrates considerable laxity in the Alexandria of Philo, provided this lynch law was confined to Jews on religious charges who were not Roman citizens, and Origen reveals a similar situation much later.
Justinian's celebrated Digest, sourcebook of Roman law, was, like the Talmud, completed about A.D. 530. Ulpian and Paulus, two leading cited authorities, flourished about A.D. 200, and formulated laws based on long precedents. Latin literature was not composed for Gospel exegesis, but its witness, if cautiously interpreted, need not be discounted.
Ulpian states that the power of Caesar's deputy may be either "pure" or "mixed." The first includes the right of inflicting the death penalty, the second stops short of this. This is further clarified by another passage, which assigns capital jurisdiction to those who rule over entire provinces. Ulpian makes it clear that with such rulers the power of death sentence is entirely personal, and under no circumstances transferable to another - yet responsible officials may not indiscriminately set at liberty accused men whose cases they cannot hear in person.
Pontius Pilate was Procurator of Judaea. In larger domains, this office might be purely financial-but Judaea was a tiny province, and Pilate was therefore invested with fuller powers, which included the ius gladii. These powers were operative strictly within his own boundaries-the moment he stepped outside them, he became a private citizen. He possessed full control over all men physically within his province, irrespective of their origin. If a Galilean remained in Galilee, Pilate could not touch a hair of his head - but let him enter Judæa, and Pilate gained absolute powers of life and death over him. These principles are clearly stated by Paulus3.
Allowing for abuses, it would seem that in her provinces Rome kept the ius gladii jealously within the hands of her appointed officials, regulating even their lawful use of it somewhat carefully. It seems almost inconceivable that the Sanhedrin alone could have executed [people] legally.
- Roy A. Stewart, Judicial Procedure in New Testament Times [Translations and emphasis mine]
Footnotes (mine):
1Babylonian Talmud:
Forty years before the destruction of the Temple, the Sanhedrin were exiled and took up residence in Hanuth. Whereon R. Isaac b. Abudimi said: This is to teach that they did not try cases of Kenas. 'Cases of Kenas!' Can you really think so! Say rather, They did not try capital charges.
[Note: V. A.Z. 8b on Deut. XVII, 10: And thou shalt do according to the tenor of the sentence which they shall declare unto thee, from that place; this implies that it is the place that conditions the authority of the Sanhedrin in respect of the death sentence. [J. Sanh. I, 1 has, 'the right to try capital cases was taken away from them, i.e., by the Romans. For a full discussion of the subject v. Juster. op. cit, II, 138ff.]]
Source
Jerusalem Talmud:
"It is taught that more than forty years before the destruction of the Temple, capital punishment was removed from Israel”
Source
2The Temple inscription mentioned above is a stone discovered by archaeologists in 1871 on the Temple Mount; it has been dated to between 23 BCE and 70 CE (the year of the Temple's destruction). It is written in Koine Greek, and reads:
ΕΝΤΟΣ ΤΟΥ ΠΕΡΙ ΤΟ ΙΕΡΟΝ ΤΡΥΦΑΚΤΟΥ ΚΑΙ ΠΕΡΙΒΟΛΟΥ ΟΣ Δ ΑΝ ΛΗΦΘΗ ΕΑΥΤΩΙ ΑΙΤΙΟΣ ΕΣΤΑΙ ΔΙΑ ΤΟ ΕΞΑΚΟΛΟΥΘΕΙΝ ΘΑΝΑΤΟΝ
"No foreigner may enter within the balustrade around the sanctuary and the enclosure. Whoever is caught, on himself shall he put blame for the death which will ensue."
Wikipedia

3 Digesta Iustiani Augusti [Digest of Justinian Cæsar]
Paulus libro 13 ad Sabinum
Praeses provinciae in suae provinciae homines tantum imperium habet, et hoc dum in provincia est: nam si excesserit, privatus est. Habet interdum imperium et adversus extraneos homines, si quid manu commiserint: nam et in mandatis principum est, ut curet is, qui provinciae praeest, malis hominibus provinciam purgare, nec distinguuntur unde sint.
The Governor of a province has authority only over the inhabitants of his province; and this only as long as he remains therein, for if he departs from it, he becomes a private person. He sometimes has jurisdiction over foreigners, when one actually commits an offence; for it is stated in the Imperial Mandates that he who presides over a province must take care to purge it of bad characters, without any distinction as to where they come from.
Source
In light of Stewart's argument above, this suggests that the even if the Romans allowed Jews to execute other Jews for religious offenses, the Roman authorities were also willing to execute gentiles for offenses committed against Jewish law.
Further support comes from Professor Lawrence Schiffman of NYU:
In fact, Roman law prohibited capital punishment at the hands of local courts such as those of the Jews. Capital punishment in any case had been made virtually impossible according Jewish law, which required that the two witnesses see each other, that the witnesses warn the perpetrator, etc. — all making it almost impossible that that Jews would have wanted to actually go through with an execution. Under Roman rule, Jews themselves, without [the Roman prefect], without the Romans, would never have been permitted to carry on capital punishment of anybody.
- Prof. Lawrence Schiffman, New York University
As Stewart and Schiffman have shown, it seems almost certain that the Jews of Judæa lost the right to conduct executions around the turn of the century, and that the Sanhedrin had, around the same time, voluntarily surrendered their authority to conduct executions. The only ways a person could be executed were to obtain the imprimatur of the Roman prefect (the legal method) or gather up a lynch mob and do it yourself (the illegal method).