It's clear from Sefer Yehoshua (Perek 19) and elsewhere in Tanach that the tribe of Shimon lived in an area scattered throughout the tribe of Yehudah. However, when the kingdom is divided between Malshus Yehudah and Yisrael, it appears as though only two tribes make up Malchus Yehudah, and Shimon is not one of them (Melachim I 12:21). Did Shimon join the kingdom of Yisrael? How did they manage to do that while living among Yehudah?
Ralbag notes this in his commentary to Melachim 12:23, and he writes that the verse does mention יתר העם in addition the tribes of Yehudah and Binyamin, which is meant to be a reference to Shimon.
From Divrei Hayamim I 4:31 it appears that at least some of the members of Shimon had movd out, with their cities being given over to the tribe of Yehudah (see Rashi and Radak there), so it could be that by the time of Rechavam there wasn't so much of Shevet Shimon left in the Judean lands.
According to Tosfos Yom Tov (Sotah 8:1), Shevet Shimon did indeed break off from Yehudah politically while remaining in the same place geographically, and so the constant infighting between the two kingdoms often took place between Yehudah and Shimon.
Sefer Shalsheles Hakabbalah (pg. 234 in the edition published in Jerusalem, 1962) writes that after successfully exiling the Northern Kingdom of Israel, Sancheirev waged war against the Kingdom of Judah, and captured several cities of Yehudah along with all of the cities of Shimon. The implication of this story is that the author (R. Gedalyah ibn Yihya) understood Shimon to belong to the Kingdom of Judah, at least with regards to the exiles of the two different kingdoms.
The tribe of Shimon was scattered through the land of Israel over time as punishment for Shimon's role in the deceit and murder of the Shechemites (Genesis 34) and for the Shimonite men committing harlotry and idolatry to Ba'al of Peor (Numbers 25). This scattering was prophesized by Jacob on his deathbed (Genesis 49). There is supposedly a midrash (maybe someone else can give a link) that states that some of Shimon's inheritance in the land passed to other tribes when the widows of Shimon remarried after their husbands were killed after the incident with Ba'al of Peor.
As you correctly point out from Joshua 19, the tribe of Shimon was given cities that were surrounded by the territory of the tribe of Yehudah. The book of 1 Chronicles 4:31 states that the Shimonites had these cities until the reign of King David. After that 1 Chronicles 4:39-43 has some of them moving to Gedor and others to Mount Seir in Edom.
Basically when 1 Kings 12:21-23 lists Yehudah and Benjamin as the two tribes who followed Rehavam and formed the Kingdom of Yehudah (Judah), it is referring to the only southern tribes that still had significant land holdings. There were probably individual members of the tribe of Shimon who still lived in the area and there were almost certainly Levites that lived in the area, but neither of them held a recognizable piece of territory. There were likely also minority populations of Gibeonites (see 2 Samuel 21) and Jebusites (see 2 Samuel 24:16) that still had a few families within the southern kingdom, but the bulk of the men and land that made up the southern Kingdom of Yehudah were of the tribes of Yehudah and Benjamin.