Presumably, the ancient Romans believed in various forms of magic. Were people who claimed to practice such magic tolerated by society, or were they persecuted like in many other ancient cultures?
Yes and no, depending on who you were, what you were doing, and how good your lawyer was.
Even in Rome's earliest law code, the Twelve Tables, there were bans against some forms of magical activity. The tables themselves only come down to us as fragments and quotations in other sources, but it seems that there were laws against magically stealing crops from other people's fields, and also against reciting evil chants (the Latin seems to have been something like mala carmina). There is a good deal of scholarly debate about exactly what actions were made illegal under these laws, and whether those actions were considered 'magic' at the time of the Twelve Tables. Carmina can be songs or poems, rather than incantations or spells, so the second law could really be against slander or gossip. Whatever the original intent, later Romans did apply these laws to magic, and indeed other laws were passed against fairly unambiguously magical activity. In 81 BC, Sulla passed a law on various kinds of homicide that included a section dealing with those who prepared, sold, bought, possessed or administered a dangerous drug (malum venenum) for the purposes of killing someone. In the modern world this would operate as a law against poisoning, but for the Romans venenum was an ambiguous word that could mean poison or magic potion. Actually in Roman thought there wasn't really a difference between the two, and they didn't have the scientific knowledge to make one. Over time, this law was gradually extended to include other malicious magical activity, for example curses and love potions.
The next source we have is a commentary on Sulla's law, possibly from the late 2nd or (more likely) the 3rd century, possibly by a jurist called Paulus:
The law now seems to have expanded to a general rule against not just malicious ritual activity but also other kinds of religious deviance - human sacrifice, temple desecration etc - and even the possession of certain books. The severe punishments were pretty standard in Roman law by this time, so shouldn't get us too excited about any kind of persecution of magicians. In other laws of the imperial period there are prohibitions on astrologers and prophets, especially when they trick the public or disturb the peace. All of these laws are still quite ambiguous, and leave plenty of difficulties for interpretation in practice. How, for example, would a judge decide if a nocturnal rite was specifically intended to enchant or transfix someone? What counts as 'magical knowledge' and how do you prove that the defendant has it or not? I'll come back to the issue of interpreting these laws later.
This is where my other two conditions come in: it mattered who you were, and how good your lawyer was. At one end of the spectrum, I have no doubt that the vast majority of magical practitioners in the Roman world went about their business totally untroubled by the law. For one thing, common magical activities like making amulets, providing herbal remedies and even most forms of divination wouldn't even come under these laws. Even if they did do something illegal, most local wise women or travelling sorcerers would have operated at such a low level that they would have been all but invisible to the authorities. It is only when individuals rose to operate among the elite that they got caught out, and the works of Roman writers like Tacitus, Suetonius and Ammianus Marcellinus are full of relevant stories. Astrologers, and those who consulted them, were punished for seeking information about the deaths of emperors, and members of the imperial household were accused of administering poisons and potions to murder their rivals.
This is where legal representation comes in. The only detailed account of a trial on an accusation of magic that we have is Apuleius' defence of himself - the whole speech can be found here: http://classics.mit.edu/Apuleius/apol.html Apuleius' had married a wealthy widow (Pudentilla) in a backwater town in North Africa. The woman's brother-in-law disapproved, and accused him of performing various nefarious actions in order to enchant her: he bought certain kinds of fish (presumably to make love potions); he had used chants to send a slave boy into a trance; he kept a secret object wrapped up among his household gods; he had performed a nocturnal sacrifice; he had commissioned the carving of a ghoulish wooden statuette to which he paid cult; and finally, he had used carmina et venena (Apol. 69.4) to seduce Pudentilla. In his defence speech, Apuleius makes expert use of the ambiguities in the laws that I mentioned earlier; all of the actions of which he was accused could be given innocent explanations. He bought those fish because he's a philosopher, interested in studying the creatures of the world. The slave was an epileptic who had a totally normal seizure. His secret objects and wooden statues were actually connected to legitimate gods or cults. It's a brilliant speech, and as Apuleius clearly published it we assume it worked and he was found not guilty. For our purposes here, it shows that legally defining magic was enormously tricky in the Roman world, even though they had clear laws against some forms of it.