While the Bible specifies the age of accession for most of the kings of Israel and Judah, Solomon's age is not given. In his dream at Gibeon Solomon describes himself as a נער קטן which may be part of the reason Seder Olam says he was twelve years old at accession. Solomon reigned for 40 years and when he died his 41-year-old son Rehoboam became king. Obviously this means Rehoboam was born one year before Solomon's accession. If we accept the Seder Olam figure, this means that Solomon became a father at the age of 11, two years before he had the legal ability to effect a marriage. That a minor cannot effect a marriage is taken as common-knowledge in the Talmud: קטן שקידש הכל יודעין שאין קידושי קטן כלום.
The question is based on the Talmud's statement that an underage boy cannot affect a marriage. This is correct, but it neglects the fact that a boy's father can affect a marriage on his behalf (Mishnah). Solomon acceded to the throne in his father's lifetime so David was certainly available to contract his marriage to Naamah when he was too young to marry her on his own.
The Gemorroh in Sanhedrin 69b brings a machloikes Beis Shammei and Beis Hillel regarding the earliest age one can father a child 8\9 years old with detailed examples from Shlomo Hameleche's mother, grandfather and great grandfather Achitofel. the Geomorroh mentions Beis Hillel opinion ובית הלל סברי לא גמרינן מדורות הראשונים 'we do not learn form earlier generations'. One can understand this to mean that the rules were different then, and in earlier generation perhaps an 8 or 9 year old could effect a marriage unlike later periods