The Republic did not even have official prosecutors, so that even crimes against the State were not prosecuted by the State. Instead, private prosecutions were brought by individuals. Men such as Cicero used this as a way to build their reputations and advance their careers, by either defending or prosecuting the accused. The American legal system is sometimes described as being legislation by litigation, and this is equally true of the Republic.
Republican punishments included exile, fines, and execution; some of these are covered in the Laws of the Twelve Tables. Executions seems to have been the most popular. Being strangled in the prison was the norm, but when one wanted to make the death more public and more shameful the victim was thrown off the Tarpeian Rock (it implied treason, but was also used for perjury which was considered the breach of an oath to Rome). Sulla particularly liked the latter method, and tried - but failed - to have it imposed on Marius [Plutarch, Sulla, 10]:
Sulla now called together the senate, and had a sentence of death passed on Marius himself and a few others, among whom was Sulpicius the tribune of the people. But Sulpicius was killed, after he had been betrayed by a servant, to whom Sulla first gave his freedom, and then had him thrown down the Tarpeian rock; moreover, he set a price on the head of Marius, an act both ungrateful and impolitic, since it was in his house that he had found refuge and surrendered himself a little before this, and had been let off safe.
Arsonists were burnt, which seems particularly appropriate as a form of punishment. Apparently singing "scurrilous songs against a citizen" - presumably by a slave or non-citizen - could result in clubbing to death if convicted. Those who stole crops were considered to have dishonored Ceres, so were hung in a special ritual as a sacrifice to her. When it came to adultery and parricide the culleus was popular - the guilty would be sown into a sack with an animal and drowned. Rome saw the chastity of the Vestal Virgins as directly linked to her prosperity, so if a Vestal broke her vow she would be 'buried' alive in an underground chamber in the Campus Sceleratus.
I have to mention apotympanismos, which was used by the Persians, then the Greeks before it was re-elaborated by the Romans into the form best known today as crucifixion. For the Romans this was a 'special' punishment reserved for the very worst kinds of crimes
The Tables only suggest imprisonment for debts (it's difficult to collect from a corpse), and then the creditor is the one in charge of the imprisonment not the state.
With time the Laws changed, and courts were instituted, but prisons never became a prominent part of the judicial system during the Republic. The tresviri capitales, best described as a proto-police force, could detain people temporarily - and so must presumably have had somewhere to detain them. With the Emperors torture, previously restricted to slaves, was introduced as a method of gaining evidence for trials. Forced labor also became a punishment; although 'new' this was in a way an extension of slavery from the captured enemy to civil matters.
Although there are few crimes for which imprisonment seems to have been the punishment, there are passing references to it in literary sources - we just can't always be sure what they mean by it. Alba Fucens had a prison in which Perseus of Macedon was held after Pydna, according to the account of Diodorus Siculus. Archaeological material is scarce.
The Carcer (prison) at the foot of the Capitoline was more formally refered to as the Tullianum. Sallust described it [Catiline 55. 3-4]:
In the prison, when you have gone up a little way towards the left, there is a place called the Tullianum, about twelve feet below the surface of the ground. It is enclosed on all sides by walls, and above it is a chamber with a vaulted roof of stone. Neglect, darkness, and stench make it hideous and fearsome to behold.
In the Imperial period Governors of provinces could order executions of non-citizens, but not of citizens - hence why St. Paul was sent to Rome, as were the Christian citizens Pliny came across in Bithynia (Epistle to Trajan, 97.66). Under the Empire the number of prisons increased - more people, more crimes, more need for prisons. Most prison legislation - proto-prison reform - began with Constantine and the Christian emperors.