According to Wookieepedia, an old anti-Sith law was added to the Republic's Galactic Constitution thousands of years before the events of the movies. This law banned the Sith religion. However, the law was removed from the Constitution before the Clone Wars so that the Constitution outlawed persecution based on religious affiliation. Wookieepedia cites the novelization of Revenge of the Sith, in which Chancellor Palpatine mentions such persecution was illegal. Consequently, it was not a crime to simply be a Sith.
If Palpatine had been brought to trial merely on the basis that he was a Sith it would not have been possible to convict him quickly. Depending on how the Republic defines treason, it may have been possible to convict Palpatine as a traitor to the Republic for working with the Separatists as Darth Sidious. However, this is complicated because Palpatine was the legitimately elected head of state of the Republic. Furthermore, as Mace Windu states in Episode III, it may have been impossible to convict him of anything:
Windu: I'm going to put an end to this, once and for all!
Anakin: You can't. He must stand trial.
Windu: He has control of the Senate and the Courts. He's too dangerous to be left alive!
The fact that Mace Windu himself didn't think Palpatine could be convicted (at least not quickly) is good canon evidence that it was not a crime to simply be a Sith (and thus Palpatine could not be quickly convicted).
Unfortunately for the Jedi, when Mace Windu attempted to summarily execute the legitimately elected Supreme Chancellor, Windu (and by extension the Jedi Order) became guilty of treason. That's certainly how Palpatine viewed it (and he's arguably right, again depending on how the Republic defines treason):
It's treason, then.
This gave Palpatine justification (as he argued it) to issue Order 66 and have the Jedi executed.