Let me back up a bit:
There were only 2 waves of persucution:
The mid-lates 60's (Nero and it was Jews who were persucuted. Christians got caught up with this sice they were Messianic-Jews or Jew loving Gentiles)
Paul probably preached in the 40,50s and early 60s.So let's start with the 40's (A reading of Galatians 1 and 2 would answer all your questions btw)
in the 40's Paul and his companions worked through Galatia, Aisia Minor and Greece. (NOTE THAT THIS IS NOT FAR AN WIDE! It is all well connected and the sea crossing in minimal)
In the late 40's Paul had to adress the issue about beleivers having died before the end came. The letter likely reached Paul in Corinth. From here Paul responded with 1 Thessalonians likely using Silas or Timothy as bearer.
Now: How did they know where Paul was? Easy. If you read Paul's letters you will find that, contrary to Acts, Paul spent many months at a time in Corinth. Likely he left Macadonia for Asia Minor to winter that year.
Next came a major issue. The churches in Galatia. It would seem that after Paul's trip back to Jerusalem and his dispute with Peter that the Jerusalem church wanted to take control of Paul's churches and make them conform to the Mosaic Law.
Now:Word would have reached Paul in Corinth easily by well travelled roads. In return Paul wrote Galatians and likely sent it by the same disciple that informed him. (Barnabbas?)
Paul travelled now to Ephesus and gave birth to a network of messages back and forth to Corinth. Schoolars refer to this as the Corinthian coorspondance and it includes 1 Corinthians and Parts of 2 Corinthians.
At this point Paul sends 2 letters to Macedionia and Achaia (2 Crinthians 8,9) requesting money for the churches in Judea. We have now reached the 60s.
Paul now does something insanely stupid and aids a felon named Philemon. Since this short letter states Paul is in chains were can determine Paul sent this letter by means of Philemon back to Onesimus in Colossee (Not far from Ephesus) and asks to not only accept his formor slave back but also to send relief. Paul also bids the Philippian church arcoss the sea for money as they are his favorite church. (Phillipains 2,3) He names Timothy as the bearer.
Paul is released but no by any help from Onesimus! The church in Phillipi bails him out. In return Paul again sends a thank yoou letter to them (Phillipians 4)
Paul now sends ahead to Rome. The Roman churches were not founded by him and for all we know this is most likely his first trip there. But the Romans have heard about Paul the crazy guy. They think he hates the law and Israel. Paul in his letter (Romans) addreses this.
And guess what!
He ends up in Rome in the heart of Nero's persucution! Uh oh. Paul is jailed and sends one final letter* to Phillipi (Phillipains 1) where his indicates he might die but to die would be gain.
* If there is a historical core to 2 Timothy chapter 1 and 4 then Paul MIGHT have sent another letter after this one but 2 Timothy was reworked into a Pastorial around 100 years later)
Note in many cases Paul was NOT being persucuted and neither were his followers. aul usually stayed in the same area of Aisai Minor or on specific routes.
Paul used his own diciples to deliver letters.
This model I have just shown where Paul doesn't travel much, uses his own disciples and only undergoes persucution from Jews and Rome (when in Rome at the end) is NOT MY MODEL!
Rather this is a recent recontruction by historians and scholars.
DO NOT USE ACTS TO RECONSTRUCT PAUL!
A good read is:
The Authentic Letters of Paul