The Romans ran both quinquiremes and triremes. The Triremes were their first attempt at naval warfare, and were a woeful failure. This was around 311 B.C.

After this, they copied the quinquireme model off of the Carthaginians, and with some slight differences to the plan made their own.

What is important to note with the quinquireme navy of the Romans is that it wasn't really built by choice: the Romans had no choice but to build a navy as the Carthaginian empire had outposts on the island of Sicily and Rome needed these removed - a task which they couldn't accomplish by land alone.

So in early spring of 260 B.C., the Senate ordered 100 quinquiremes built and twenty triremes, all to be ready by summer. This was the Senate calling for an entire Navy to be built, and crews formed, within the space of three months. It was accomplished with the help of Greek sailors from cities Rome ruled in Southern Italy, and the crews were made up of Greek allies for the triremes, and subjects from outside of Rome for the quinquiremes.

The reason for differences in crew origins was simply because the quinquiremes rowing action required much less skill to master than the triremes. The Greeks were accomplished sailors, so they were used for the more difficult triremes.

The structure of the quinquireme designs was altered for two reasons: firstly, the Carthaginians were much more competent sailors, who were able to maneuver extremely well, and thus used lighter ships, which were consequently harder to handle. Secondly, the Romans had the corvus - the ramp attached to the ship to allow Roman ships to clamp Carthaginian ships in place while the legionnaires swarmed across to capture the ship. The ramps added a great deal of weight to the ships, and altered the centre of gravity. A change in weight distribution was necessary to prevent the ships capsizing.

So the Romans at this point(260 B.C.) had some 100 quinquiremes and 20 triremes. Each quinquireme had 300 oarsmen, 40 fighting men, 80 legionnaires and whatever assorted crew was added on in the form of officers. The total was probably just above 420. The triremes had a rowing crew of 170, but I'm not sure on the specifics of their fighting crews. I presume they had the standard 40 men, but I'm not sure whether they were equipped with a corvus as well.

The first Punic War lasted twenty three years, and during the course of it, both sides lost hundreds of ships. The Carthaginians lost theirs in attacks by the Roman navy, who had sheer weight of numbers to overrun them. The Romans however, lost theirs in storms.

After capturing 114 Carthaginian ships and sinking around 20 more, the Roman fleet lost 250 ships and around 100,000 men in a storm. This was what made the Roman fleet so astonishing. They had an unprecedented production of ships, and then managed to keep them afloat through battles despite their inexperienced naval force, but then lost the majority of their ships to the weather because their men weren't able to read the ocean like other sailors.

By the end of the war, the Carthaginian navy was effectively eliminated, and the roles had reversed: From Carthaginian superiority to Roman superiority. It took less than half a century. After the Punic Wars, Rome turned to war in the East and this time the Navy was much lessened, to the point where Roman allies in Rhodes were called upon to provide naval support. Rome dominated the Mediterranean, but they were never comfortable on the sea, and it's shown through the rapid dismantling of their navy.

Source: Lionel Casson's The Ancient Mariners

If you're interested in fiction surrounding this topic as well, John Stack has an excellent trilogy called Masters of the Sea. It follows a young Greek sailor as he rises through the Roman navy from its inception and into the Punic War.

EDIT: sniped by /u/McGuineaRI! Hopefully I added in some helpful additional stuff though.

The first vessel launched by the Romans that could really be considered a warship was the Quinquireme which held ~420 crew. They figured out how to build these during the first Punic War when they found a Carthaginian ship grounded (or trapped among rocks near a point) intact in the waters off Sicily. It was meticulously taken apart and reverse engineered. Over a hundred were built and manned by sailors that learned how to sail and row in unison on land by pantomiming the actions using props. The Carthaginians were shocked to discover that their dominance over Mediterranean trade routes was being violently questioned by Rome. I'm sure they were even more shocked when the Romans actually put up a fight and ruined their fleet.

The Carthaginian navy fought very differently than the Roman navy. The Carthaginian Quinquireme was used as a very swift and massive ram. The rowers would work together to position the bow of the ship pointing towards a vulnerable part of an enemy ship then rowing crews on both sides would row full speed ahead. The massive bronze ram fastened to the front of the ship just below the water line would puncture the hull and send the opponents' ship down into the depths. The Romans had other plans. The heavy infantry the Romans had is arguably the greatest asset they have at their disposal. In order to bring this heavy infantry to battle with the Carthaginian's star asset they had to get creative with the way they conducted naval warfare. They mitigated this problem by building retractable ramps that would drop down on the deck of the enemy's ship and hold it in place while the infantry streamed over to the other side. The Carthaginians weren't prepared for this and the marines on board couldn't handle the onslaught. This is why during the Battle of Cape Ecnomus (the first large scale sea battle between Carthage and Rome that I've been describing) so many Carthaginian ships are captured and a similar number are sunk. It makes sinking all those beautiful ships seem like a real waste. This is where the Romans became a seafaring power; a distinction they wouldn't give up for centuries.

What I described is the state of the Roman navy during the Republican era. Because I'm not acquainted with the Roman navy during the Principate and Dominate or even later I won't get to much into it. Roman history begins with the founding of the Republic in 509 BCE and ends with the conquest of Constantinople by the Ottomans in 1453 CE. There was a lot of changes during this time so you're going to want to narrow down the time frame you're interested in so you can nail down a starting point.

To learn more about the beginning of the Roman Navy and their first engagement with their Carthaginian counterparts click this link here. That is The Histories by Polybius. I suggest you start at paragraph 1 but the naval stuff picks up in the paragraphs in the 20's. It's really interesting to read and even more so because it is written by a man of that time.

So you've gotten answers so far only about the very earliest period of the Roman fleet. The Roman fleet, unlike the army, was highly variable and by no means standardized, nor was there a particularly strict set of laws governing its recruitment and organization the way we find with the army. While the answers are good, they leave out the important fact that frankly we know very very little about the Roman fleet directly. Most of what we "know" is assumed to be true due to comparisons with the better-documented fleets of Roman contemporaries, rather than from the Romans themselves--assumptions which are usually pretty good, since ancient fleets really didn't differ much, although of course exact details about a lot of fleets are hard to come by. The fleet of the Punic Wars was incredible, but it was very much an anomaly, a force created for a specific purpose and disbanded immediately thereafter, as such a large fleet was incredibly expensive and required a commitment by the state and people to maintain it with money, constant maintenance, and experienced and complete crews. The drain on the state would have been quite noticeable, and unlike Athens during the 5th Century or Carthage it was not necessary.

Roman fleets were not standardized until the Principate, when Augustus created a small force of a handful of small standing fleets, which were mainly posted at corners of the Mediterranean and mainly served to deter pirates and provide support to ground troops rather than go off and fight major naval campaigns by themselves. Until then Roman fleets were raised and disbanded as needed, and almost never by the Italians themselves. Provincial governors and other magistrates with imperium could raise naval forces whenever they pleased, usually by calling up a levy from allied or subject cities--this is how Piso raised the modest fleet that Cicero accuses him of raiding the Black Sea with. These naval forces tended to return to their parent cities once the campaign was over, and indeed the Romans relied heavily on their provincial and allied cities to patrol the Mediterranean for them, sweeping for pirates and the like. Obviously this didn't always work, and sometimes it backfired (arguably Roman policy with Rhodes caused a lot of Rhodians to resort to piracy), but it was highly economical to essentially outsource such an expensive duty on cities who were prepared to shoulder it and only had to take up a piece of the burden, rather than the whole thing. Even when Romans raised enormous fleets, such as Pompey's fleet against the pirates, it mainly came from allies--Pompey's fleet was composed almost entirely of Greek vessels, and both Antony and Octavian fielded mainly allied warships at Actium, Antony's coming from his Greek, Anatolian, and Syrian provinces (or from Egypt) and Octavian's coming mostly from the Adriatic area. We do have evidence for large Italian fleets being raised and kept for some time, however. For example, the Republican fleet that Sextus Pompey later took over was probably composed mainly of Italian ships, probably built specifically for the purpose of keeping Caesar from crossing over into Greece (he barely slipped by them anyway though), and Octavian commanded a large number of Italian vessels at Actium, most gotten from defecting Republican crews.

Roman warships were outfitted very differently depending on their purpose. Frequently the allied fleets were allowed to furnish themselves as was their custom, without Roman interference. When fleets were undertaking important actions or coming directly under Roman supervision it appears that really the only important change was the presence of Roman officers and of Roman marines. The use of heavy infantry marines is hardly an innovation of Roman origin, nor is the use of massed marines--the Greeks were putting hoplite marines on their ships centuries earlier (the Athenians had a particularly fearsome marine force, which terrified the Peloponnesians on land and sea) and Lade the Chiots fielded 40 marines, a ludicrously large number for little triremes, on each ship. Nor did the Romans come up with the idea of going for boarding actions rather than outright ramming--until the Athenians perfected the concept of fast, light vessels that could build up enough speed to reliably cripple an enemy warship with a single ram (and get out before being boarded) the standard tactic with triremes was to ram and board, as ramming almost never resulted in a ship sinking or even being too badly damaged to be scrapped. What shocked the Carthaginians when the Romans boarded them during the Punic Wars is that the Carthaginians didn't do that, although plenty of other people did--the Carthaginians relied on ramming tactics, which was a rarity. The amount of marines on a Roman warship is not well documented, and probably differed greatly. A quinquireme could easily field several dozen, though, and Roman warships tended to be build with large decks and castles to allow more soldiers on board. Scipio's fleets in Spain were probably jam-packed with marines bursting the gunwales (it's likely he had at least a hundred on each ship), as he would beach his ships and use the marines to construct extra centuries sometimes. But this was probably somewhat abnormally large, and we don't have any good reason to believe that Pompey's fleets fielded as many marines, although Pompey was also transporting troops by sea so it's possible that some of his ships were over-manned with troops, but more or less impossible to know. Certainly Octavian's little Liburnian galleys, which were a sort of light bireme, fielded no large force of marines--indeed, they may not even have had rams with which to attack, possibly relying entirely on missiles