The Correspondence of Paul and Seneca is a work of fourteen letters purporting to be, as one might expect, a correspondence between Seneca and St. Paul, who were indeed contemporaries. We have external attestation of a work at least along these lines in the fourth century, as both St. Jerome (De viribus 12) and St. Augustine (Epistle 153) mention a supposed correspondence between Paul and Seneca that was read at the time, and the work that we have is generally assumed to be (at least some version of) the same one, which generally leads people to assume that it is a fourth-century work (although scholars have at various times proposed that some of the letters in the collection were added later). It was fairly widely copied, and we have manuscripts of it going back to the ninth century, in manuscript lines that arguably go back at least to the fifth century; what we have of the text is not always high quality or in good shape, so there are a number of difficulties in interpreting and translating it.
The work is often disparaged as intellectually unimpressive, and it is generally agreed that it has a rough style, but the letters for the most part show a fairly good knowledge both of Rome and of events in the reign of Nero. It has also been criticized for being fairly substanceless, consisting mostly of Seneca and Paul complimenting each other, but I think this is generally due to a sort of philological shortsightedness; as an epistolary work, one should not be looking so much at individual letters but at the whole -- in a short epistolary work consisting of short letters, each letter is not going to contribute much, but they may well work together to build something definite. And I would suggest that this is in fact true of the Correspondence: the work should be seen as an epistolary narrative, building by various techniques of suggestion and allusion a story in the gaps between the letters. In any case, I will be reading it as an epistolary short story here.
You can find The Correspondence of Paul and Seneca online in a number of places; a particularly handy one is this Latin-English parallel version, using the M. R. James translation. There is elsewhere a translation by Jeremiah Jones, which has some differences. Lightfoot has a good discussion of the background in his Dissertations on the Apostolic Age.
Letter I: Seneca writes to Paul about a discussion he had with his friend Lucilius and a number of others, including some Christians, who happened to meet up with them in the Gardens of Sallust; he assumes Paul has been informed of the discussion, and lets Paul know that they had wished he had been there in person. A book collecting some of Paul's letters had been read, and Seneca remarks that they were mira exhortatione vitam moralem continentes, i.e., they contain wonderful exhortations to the moral life ("inculcate the moral life with admirable precepts" in James's translation). Seneca takes them not merely to be Paul's advice, but to be Paul drawing on the wisdom of ages.
--- The reference to Paul's letters being bound in a book is often taken to be a sign of the work having been written later, since it is generally thought that this practice only began well after the lifetime of Paul and Seneca.
--- Lucilius Junior was procurator of Sicily and a friend and correspondent of Seneca.
--- The Gardens of Sallust were a park in northeastern Rome; they were severely damaged in the sack of Rome in 410 and vanished entirely in the sixth or seventh century.
Letter II: Paul replies, saying he would have sent his letter sooner if he had had the young man he meant to send to Seneca, "For you know when, and by whom, and at what moment, and to whom things ought to be given and entrusted." Paul is happy with Seneca's good opinion of his work, since he knows that a censor sophista magister tanti principis etiam omnium, a censor/sophist/teacher of such a prince and indeed all, would only say such things if they were true.
--- Here we have the first allusion to Nero who will, of course, play an important role in the unfolding of the correspondence.
--- Paul's comment about the young man is interestingly indirect and cirumspect; the young man is treated as important and known to Seneca, but deliberately not named. This is something that we find repeatedly in the correspondence: Seneca and Paul will talk about a matter as if they both know more than is explicitly said and as if they both are deliberately not putting something down in writing -- we saw it with Seneca's remarks about the Christians in the first letter, and we will see it several times again.
Letter III: Seneca writes that he has put together a book collecting together various writings and intends to read it to Caesar, if he can, and perhaps Paul himself will be present. If not, they will get together sometime to look over the work together. Seneca has intended to get Paul's opinion on the book before he gives it to Caesar, if it could be done without risk safely.
--- I haven't been able to find anyone who even remarks on it, but I suspect we should take the remark about meeting without risk as a sign that there is, again, more going on here than is explicitly said.
Letter IV: Paul remarks that whenever he reads Seneca's letters, it's as if Seneca were there, and, as soon as Seneca begins to come, they will see each other.
Letter V: Seneca asks why Paul stays away. He suggests that it may be the indignatio dominae, the wrath of the Lady, because Paul has left the old rite and sect and converted others, but says that it may be possible to plead with her.
--- If the translations are any guide (they vary widely), the text to this letter must be somewhat difficult to pin down. However, the reference to Poppaea seems clear enough, even though some translators don't seem to make this explicit. Poppaea Sabina the Younger became Nero's second wife in AD 62. Contemporary accounts of her are often contradictory, but at least some of them indicate that she did indeed have sympathy for the Jewish people and religion -- Josephus, who had met her, certainly thought so.
Letter VI: Paul says that he cannot talk about the subject Seneca has raised in writing, especially since he knows that there are people in both his and Seneca's circle who would know what he is talking about. He concludes instead by saying that honor must be paid to all because some people take offense, but if we are patient with them, then if they can repent, they can be overcome.
--- Here we have Paul explicitly saying that he cannot write openly about the real matter of discussion between them.
Letter VII: Seneca is content in reading Paul's letters to the Galatians, to the Corinthians, and to the Achaeans. He remarks that there is a holy spirit in and above Paul that expresses the thoughts in them. He wishes Paul's style had the excellence appropriate to such majestic thoughts, and then casually remarks that Nero was moved by Paul's thoughts, and had been surprised to find such ideas in someone who had not had a regular education. To this Seneca had replied that the gods often speak by the mouths of the guiltless, and had given him the example of Vatienus, a simple man who had conversed with Castor and Pollux. Nero had been convinced by the argument.
--- The remark about the 'holy spirit' might be thought a Christianization, but in fact it is an expression used by Seneca himself in one of his letters to Lucilius (Epistolae Morales 41).
--- Vatienus is said to have met two handsome men who told him that Paullus had taken the king of Persia prisoner. Perhaps significant in light of Paul's life, Vatienus, when he brought this news to the Senate, was thrown into prison for having wasted the Senate's time, until it became clear that the two men had really been the gods Castor and Pollux.
Letter VIII: Paul writes back that although he knows that Caesar, despite his lapses, loves things to do with Christians, he will admonish Seneca. Seneca should not have brought the matter to Nero's attention given that he was not properly prepared, being a worshipper of the gods of nations, and Paul begs him not to do it again. It is important not to offend Poppaea. The last part of the letter is obscure, but I take it that it is intended to convey the idea that it is less Poppaea's anger than her taking offense that is a problem.
Letter IX: Seneca says he knows that Paul is not disturbed on behalf of himself but due to the moral situation. They should then start anew, and Seneca asks that if anything was done carelessly, it should be pardoned. Seneca is sending Paul a book, De copia verborum.
--- While there are later books that were spuriously attributed to Seneca under the title, De copia verborum, we don't know if the letter is referring to such a book or something else.
Letter X: Paul remarks that if he doesn't put Seneca's name first in the heading of the letter, he does something unfitting. He ought instead to be all things to all men and to respect Seneca's senatorial position. He adds a date: the fifth of the calends of July, in the consulate of Nero and Messalla.
--- Paul talks about being all things to all men in 1 Corinthians 9:22: " I have become all things to all people, that I might by all means save some."
--- Nero and Marcus Valerius Messalla Corvinus both served as consuls in AD 58. (It is perhaps worthwhile to note that Nero's wife at that time would have been Claudia Octavia, not Poppaea.)
Letter XI: Seneca responds that it is an honor to be so closely associated with Paul, and that Paul is worthy to be named first in the headings of letters, particularly since he is a Roman citizen. As to rank, he wishes Paul and he could switch places. The letter is dated: the tenth of the calends of April, in the consulate of Apronianus and Capito.
--- Gaius Vipstanus Apronianus and Caius Fonteius Capito served together as consuls in AD 59.
Letter XII: Seneca writes again, grieving that so many Christians suffer, and that the Romans think them the cause of every ill that befalls the city. Previous eras had to bear Alexander the Great or Dionysius, and ours has to endure Caesar. The source of the fires in Rome is obvious, and if people could speak plainly, it would be clear to all. Christians and Jews are commonly blamed for it, but the criminal who did it will eventually receive his reckoning, and as the best is sacrificed for the many, he too will be burned. In six days 132 houses and four apartment blocks have been incinerated. The date is: the fifth of the kalends of April, in the consulate of Frugi and Bassus.
--- The Great Fire occurred in July of AD 64 and lasted six days. Nobody knew its source but the usual suspect is Nero himself. It's notable that this letter pretty clearly indicates that Nero is the culprit, despite again not explicitly writing it down.
--- Gaius Laecanius Bassus and Marcus Licinius Crassus Frugi were consuls together in AD 64.
Letter XIII: Seneca writes to Paul saying that his works discuss things that are rich with allegory and enigma, and therefore they should be expressed with care. Nor should Paul worry about what he has sometimes said, that worrying about such things leads to weakening the force of what is said. He should give beauty to the nobility of his words, in accordance with his great responsibility. The date is always translated as the day before the nones of June in the consulate of Leo and Sabinus; since there was no consul Leo, this is often considered a gibberish date. But it seems clear that this is a corruption that entered somewhere down the line, and it should read the consulate of Lurco and Sabinus.
--- Aulus Petronius Lurco and Aulus Paconius Sabinus were both consuls in late AD 58, serving as subsitutes for the previous consuls.
Letter XIV: Paul writes to Seneca saying that revelations have been given to him that God has granted to few. Paul sows not corruptible matter but the abiding word, which grows and endures forever. Seneca's prudence has brought him to this, to recognize that the laws of the Israelites and of the nations are to be cast aside. Seneca himself may be renewed as an author, presenting the unblameable wisdom of Jesus Christ in rhetorical form; he has come close to it, and may instill it into the temporal ruler and his household. Such a persuasion will be a difficult task, for many of them will hardly listen, but the word of God once instilled makes a new man without corruption, an enduring spirit speeding to God. The date is the kalends of August in the same consulate as the previous.
I suggest two things for reading this work; while I am by no means expert on anything to do with these matters, I think they follow quite clearly from the internal logic of the work as a whole.
(1) I think Letters XIII and XIV are displaced. They should in fact both be placed between Letters IX and X. In Letter X, Paul worries about the impoliteness of putting his name first in the heading of the letter; but in fact the only letter in which his name comes first is Letter XIV, which is clearly responding to Letter XIII. In addition, if the consulate is supposed to be that of Lurco and Sabinus, as I think it must be, then all end up being in the same year. (A potential problem, for which I have no solution, is that Lurco and Sabinus then seem a little too early in the year and Nero and Massalla's consulship seems a little late, and their order is reversed. Also, of course, all the other letters suggest dates in the 60s, with the apparent references to Poppaea and the undeniable reference to the Great Fire, not around 58, which is what the consulate dates suggest.)
(2) Putting these in proper order, we get an intelligible story arc, the tale of a noble conspiracy of morality that, alas, fails. Seneca and Paul both have reasons to worry about Nero, and through their interconnections, they start a sort of conspiracy to improve Caesar morally (I & II). Seneca's plan is to put together a morally edifying work with the help of Paul (III) and Paul agrees to this (IV), but this is complicated by the fact that Poppaea's Jewish sympathies could perhaps cause problems for Paul (V); Seneca thinks this can be overcome, but Paul can't talk about it in writing because it could not be secret (VI); he hints at his own attitude, however, in noting that they should avoid offense and be patient. Seneca, however, does not wait, and springs the plan on his own by reading passages from Paul's letters to Nero (VII), and he thinks it was successful, although he wishes Paul's letters were more stylistically impressive. Paul is not happy with this failure to heed his advice (VIII). Seneca does not take offense at this, and suggests they start again (IX); he is sending a book on improving one's style. Apparently having heard through their common connections that Paul thinks concern with style detracts from the message, he raises again the problem that Paul's style is getting in the way of conveying his message (XIII). Paul, however, reiterates his commitment to the content of his message rather than corruptible things like style, and suggests that Seneca himself is in the position to do what he is asking Paul to do (XIV). Paul seems, however, to have regretted the peremptory and commanding tone of the letter, and writes again, more or less apologizing (X). Seneca does not take offense at this (XI). However, unfortunately they have run out of time. Nero has set fire to Rome and is blaming the Christians (XII). That's an abrupt and depressing place to end, but since Paul's martyrdom has historically been thought to have taken place at some point after the Great Fire of 64 but before the end of Nero's reign in 68, I think we can perhaps take this work to be suggesting that Paul himself will be martyred in the aftermath. I think you can even see the whole set of letters as implying that Seneca, by a mistake arising from his impatience in talking about Christian doctrine with the Emperor, is the one who set Nero on the idea of blaming the Christians for the fire, and thus is, tragically, the reason for Paul's death. Since the Pisonian conspiracy to assassinate Nero occurs in 65, and Seneca was ordered by Nero to commit suicide as being suspected of involvement in that conspiracy, it is possible to read it as suggesting that Seneca may have already been making Nero suspicious of his activities.
Of course, we have to be careful; the text we have may be corrupted, and some of the letters, especially XIII and XIV, are thought to be later additions, so there is a limit to both precision and accuracy in interpretation here. But I think the epistolary story approach works very well.