Rome did in fact have something akin to a “postal service” as you put it, although it was less open to the public and run differently. As such, Paul’s letter did not go through the “post office” but instead private carriers which I will touch on at the end. So really you have two questions: how did Paul's letter arrive, and did Rome have a postal service.
WIth respect to the latter first, The cursus publicus, was primarily a means of government communication that later expanded into the movement of officials and freight such as tax collections or even books and luggage. It is believed to have played a vital role in exercising Roman rule throughout the empire and has evolved into the modern “post office” or “government post.” There don’t seem to be sources that refer to it as the cursus publicus until later in the empire, where it is mentioned in a chapter in the Life of Augustus by Suetonius which proclaims that Augustus himself established it. The reasons for its creation?
So that he [Augustus] quickly and easily could receive reports of events in every province, he stationed first young men, and later carriages, at points along the military roads. The latter system proved itself more advantageous, because then the same courier could deliver the message to its destination and, if necessary, also personally be questioned.( Suetonius (Aug. 49.3))
There were two methods of transport: first, young men acting like runners who passed messages from one station to the next. For examples, imperial bodyguards such as speculators praetorii, tabellarii Augusti and cursores (both professional couriers) and other soldiers were all transporters of messages. Provincial governors preferred to entrust messages to members of their personal staff such as beneficiarii or guard cavalrymen (equites singulaers). This system was considered poor because it meant the final messenger had no supplemental information about the messages’ content and couldn’t answer questions for example about the conditions from which it originated. This was later improved to have vehicles so that a single messenger would be able to travel all the way to the destination. Thus, it was really a courier service with added speed and infrastructure.
The second system remained in effect throughout the latter period and was far broader than just official mail. The vehicula , referring to anything from animals to boats to usually wagons, could carry baggage, freight, and messages. This was the beginning of a transition from courier to transportation network. There are even official decrees (in both Greek and Latin) declaring that no person shall use the wagons free of charge. However, it wasn’t state owned wagons with state employed messengers (think USPS today). Instead:
Since the indiscipline of certain persons calls for immediate punishment, I have caused to be posted in the various cities and villages a schedule of those services which, according to my decision, must be provided . . . The people of Sagalassos must provide a service of ten wagons and as many mules for the necessary use of the travellers and they shall receive from each user ten asses per schoinum for a wagon and four asses per schoinum for a mule.
It was broken down into local populations and each provincial governor was tasked with designating the services and creating compensation. Really, it was closer to forced rental of vehicles and animals at better than market rates. In addition, the services were limited mainly to those of wealth, power, or military service. Notable allowed were those traveling on military service, roman senators, roman knights, and centurions. For most of the time, quarters (housing and meals) had to be provided free for those on imperial business. Eventually, payment of compensation for transportation appears to have dissipated by the 4th century, but the system remained similar.
For convenience and efficiency, rest and relay stations were built along major highways of the empire, eventually being called mansiones or mutationes, in late antiquity. It was strictly forbidden to requisition animals from villagers or peasants. Constantine notably sanctioned this presumably common abuse with the threat of arrest. During this abeyance in late antiquity, the burden fell completely on the inhabitants to maintain the way stations and care for the animals.
This system notably was used to transport tax money as one of its primary functions during the late imperial period. Otherwise, freight transport was a relatively unimportant role in the cursus publicus. Constantine once had 50 of the most useful theological books sent to him at Constantinople in two government wagons for example.
Now to your question of Paul’s letters. New Testament scholars have begun more recently to examine how the biblical compositions were disseminated, particularly in a largely illiterate society. Additionally, there is added ambiguity in ancient Greek writing: punctuation, headings, paragraphs, capitalization, and no spaces between words are all logistical issues that make letters of the time incredibly hard to interpret consistently. Additionally, papyrus scrolls were unwieldy, particularly if you wanted to read from them. Some scholars seem to believe that if the roll was used by an orator, it was used more as a prop than as a set of notes.
As for the letter deliveries, Paul makes it clear for his letter to the Corinthians:
“But God, who consoles the downcast, consoled us by the arrival of Titus, and not only by his coming, but also by the consolation with which he was consoled about you, as he told us of your longing, your mourning, your zeal for me, so that I rejoiced still more” (2 Cor 7:6-7 NRSV).
It appears that it is unclear to what extent Titus was the letter carrier for others versus the extent to which Paul utilized other "Pauline letter carriers” as they are referred to now. The Oxyrhynchus papyri has other mentions of letter carriers, but there are not other “name drops” if you will like that of Titus. As for the role of the carrier, it is unclear if their role was simply to find a literate person in the congregation to whom the scroll could be trusted, or if they were to serve as interpreters or even presenters and orators of the content.
As for the mechanism of transfer at the jail, I cannot say and will defer to other commenters more knowledgeable about jailing during the time period.
Further Readings:
Johnson, L.A. (2017). Paul’s Letters Reheard: A Performance-Critical Examination of the Preparation, Transportation, and Delivery of Paul’s Correspondence. The Catholic Biblical Quarterly 79(1), 60-76. doi:10.1353/cbq.2017.0003.
E. W. Black (1995). Cursus Publicus: The Infrastructure of Government in Roman Britain. British Archaeological Reports Limited. The University of Michigan.
Lemcke, L. (2013). Imperial transportation and communication from the third to the late fourth century: the golden age of the cursus publicus.
Kolb, A. (2015). Communications and mobility in the Roman Empire. In The Oxford Handbook of Roman Epigraphy.
Adams, C., & Laurence, R. (Eds.). (2001). Travel and Geography in the Roman Empire (1st ed.). Routledge. https://doi-org.ezproxy.cul.columbia.edu/10.4324/9780203995594
I have answered this question in an earlier thread, while it does not directly address or touch on Paul's situation, it does tackle how mail and sending information worked during the Late Republic and the Early Empire. I tired to especially tackle distances and how long it would take to cover them in the Roman Empire.