score:17
I got most of this information by perusing Wikipedia.
Simon Peter (brother of Andrew) - traditionally said to be buried in Rome, under St. Peter's Basilica. The tomb dates between 130 and 300.
James (son of Zebedee and older brother of John) also called "James the Greater" - as the patron saint of Spain, he is said to have been buried in Santiago de Compostela after his remains were carried there when he was beheaded in Jerusalem. The pilgrimage site originated in the 9th century.
John (son of Zebedee and brother of James) - traditionally said to have been buried in Ephesus. The basilica has been there since the 6th century, but his remains are said to have not been found.
Andrew (brother of Simon Peter) - traditionally said to have been buried in Patras, Greece. In 357 the relics were transferred to Constantinople. In 867 the skull was sent back to Patras, and in 1208 those that remained in Constantinope were sent to Amalfi, Italy. In 1908 all relics were returned to Patras.
Philip of Bethsaida - traditions say he was martyred in Hierapolis, and archaeologists claim to have found his tomb in 2011. Santi Apostoli is said to contain his remains now (having been transferred from the tomb to Constantinople and then there before the tomb was discovered). It's unclear to me when the remains are supposed to have been transferred there.
Thomas (Didymus) - there are a number of places associated with his martyrdom and burial, but the most commonly accepted seem to be a martyrdom on St. Thomas' Mount in India and burial nearby where San Thome Basilica was later erected. It's unclear when exactly the site became associated with him, but it appears to have been 1523 at the latest.
Bartholomew (Nathaniel) - said to have been martyred in Albanopolis, Armenia with his remains being shuffled around for a while later until they came to rest in the Basilica of St. Bartholomew in Rome in 1180.
Matthew (Levi son of Alphaeus) of Capernaum - said to be buried in Salerno, Italy, where a cathedral was built in 1076.
James (son of Alphaeus) also called "James the Lesser" - Hippolytus said he was stoned to death in Jerusalem, but Nikephoros said he was crucified in Ostrakine, Egypt. His relics are in Santi Apostoli with Philip. As with Philip, it's unclear to me when the site became associated with him.
Simon the Zealot - relics are in St. Peter's Basilica in the same complex as Peter (so dated between 130 and 300)
Judas Thaddaeus (Lebbaeus), called "Jude of James" (brother or son of someone named James, possibly one of the Jameses in this list) - relics are in St. Peter's Basilica in the same complex as Peter (so dated between 130 and 300)
Judas Iscariot - died in Akeldama and presumably still there, but nobody has been terribly interested in venerating the tomb of a traitor
Matthias - the Greeks claim he's buried in Gonio, Georgia but Catholics have had his relics in St. Matthew's Abbey in Trier, Germany since 1148