Seems like the entry in the Catholic Encyclopedia could be very useful here:
http://www.newadvent.org/cathen/11567b.htm
In fact, I'll risk a three-paragraph copy/paste here as there is a lot of information to wade through on the linked page:
"
E. Last Years
This period is wrapped in deep obscurity for, lacking the account of the Acts, we have no guide save an often uncertain tradition and the brief references of the Pastoral epistles. Paul had long cherished the desire to go to Spain (Rom., xv, 24, 28) and there is no evidence that he was led to change his plan. When towards the end of his captivity he announces his coming to Philemon (22) and to the Philippians (ii, 23-24), he does not seem to regard this visit as immediate since he promises the Philippians to send them a messenger as soon as he learns the issue of his trial; he therefore plans another journey before his return to the East. Finally, not to mention the later testimony of St. Cyril of Jerusalem, St. Epiphanius, St. Jerome,
St. Chrysostom, and Theodoret, the well-known text of
St. Clement of Rome, the witness of the "Muratorian Canon", and of the "Acta Pauli" render probable Paul's journey to Spain. In any case he can not have remained there long, for he was in haste to revisit his Churches in the East. He may have returned from Spain through southern Gaul if it was thither, as some Fathers have thought, and not to Galatia, that Crescens was sent later (II Tim., iv, 10). We may readily believe that he afterwards kept the promise made to his friend Philemon and that on this occasion he visited the churches of the valley of Lycus, Laodicea, Colossus, and Hierapolis.
The itinerary now becomes very uncertain, but the following facts seem indicated by the Pastorals: Paul remained in Crete exactly long enough to found there new churches, the care and organization of which he confided to his fellow-worker Titus (Tit., i, 5). He then went to Ephesus, and besought Timothy, who was already there, to remain until his return while he proceeded to Macedonia (I Tim., i,3). On this occasion he paid his promised visit to the Philippians (Phil., ii, 24), and naturally also saw the Thessalonians. The letter to Titus and the First Epistle to Timothy must date from this period; they seem to have been written about the same time and shortly after the departure from Ephesus. The question is whether they were sent from Macedonia or, which seems more probable, from Corinth. The Apostle instructs Titus to join him at Nicopolis of Epirus where he intends to spend the winter (Titus, iii, 12). In the following spring he must have carried out his plan to return to Asia (I Tim, iii, 14-15). Here occurred the obscure episode of his arrest, which probably took place at Troas; this would explain his having left with Carpus a cloak and books which he needed (II Tim., iv, 13). He was taken from there to Ephesus, capital of the Province of Asia, where he was deserted by all those on whom he thought he could rely (II Tim., i, 15). Being sent to Rome for trial he left Trophimus sick at Miletus, and Erastus, another of his companions, remained at Corinth, for what reason is not clear (II Tim., iv, 20). When Paul wrote his Second Epistle to Timothy from Rome he felt that all human hope was lost (iv, 6).; he begs his disciple to rejoin him as quickly as possible, for he is alone with Luke. We do not know if Timothy was able to reach Rome before the death of the Apostle.
Ancient tradition makes it possible to establish the following points: (1) Paul suffered martyrdom near Rome at a place called Aquae Salviae (now Tre Fontane), somewhat east of the Ostian Way, about two miles from the splendid Basilica of San Paolo fuori le mura which marks his burial place. (2) The martyrdom took place towards the end of the reign of Nero, in the twelfth year (St. Epiphanius), the thirteenth (Euthalius), or the fourteenth (St. Jerome). (3) According to the most common opinion, Paul suffered in the same year and on the same day as Peter; several Latin Fathers contend that it was on the same day but not in the same year; the oldest witness, St. Dionysius the Corinthian, says only
kata ton auton kairon, which may be translated "at the same time" or "about the same time". (4) From time immemorial the solemnity of the Apostles Peter and Paul has been celebrated on 29 June, which is the anniversary either of their death or of the translation of their
relics. Formerly the pope, after having pontificated in the Basilica of St. Peter, went with his attendants to that of St. Paul, but the distance between the two basilicas (about five miles) rendered the double ceremony too exhausting, especially at that season of the year. Thus arose the prevailing custom of transferring to the next day (30 June) the Commemoration of St. Paul. The feast of the Conversion of St. Paul (25 January) is of comparatively recent origin. There is reason for believing that the day was first observed to mark the translation of the
relics of St. Paul at Rome, for so it appears in the Hieronymian Martyrology. It is unknown to the Greek Church (Dowden, "The Church Year and Kalendar", Cambridge, 1910, 69; cf. Duchesne, "Origines du culte chrétien", Paris, 1898, 265-72; McClure, "Christian Worship", London, 1903, 277-81).
"