Why did Clement and Eusebius believe that Paul was married? In an answer to a related question (What is the evidence that suggests that the Apostle Paul was married?), I encountered the following quote from Eusebius:


  Clement, indeed, whose words we have just quoted, after the above-mentioned facts gives a statement, on account of those who rejected marriage, of the apostles that had wives. "Or will they," says he, "reject even the apostles? For Peter and Philip begot children; and Philip also gave his daughters in marriage. And Paul does not hesitate, in one of his epistles, to greet his wife, whom he did not take about with him, that he might not be inconvenienced in his ministry." (Church History, 3.30, emphasis added)


I'm not aware of any biblical passage where Paul greets his wife.  The closest thing I can see, given the context, is 1 Corinthians 9:5:


  Do we not have the right to take along a believing wife, as do the other apostles and the brothers of the Lord and Cephas? (ESV)


But there's nothing here about greeting a wife, or having one at all.  Plus, two chapters earlier, he writes:


  To the unmarried and the widows I say that it is good for them to remain single as I am. (1 Co 7:8, ESV)


So what gives?  What could Clement/Eusebius have been referring to?  A biblical text of which I am unaware?  Some early apocryphal work?  

Is there any tradition, or scholarly opinion, of what text Clement of Alexandria is referring to?
Clement of Alexander likely was referring to Philippians 4:3


  Yes, I ask you also, true companion (σύζυγε), help these women, who have labored side by side with me in the gospel together with Clement and the rest of my fellow workers, whose names are in the book of life. (ESV)


The word σύζυγε (lexical form σύζυγος) is a hapax legomenon within the New Testament.  Outside the New Testament, it is used as a term of flattery by Julius Caesar and other emperors.  It is also used to describe competing gladiators (the opponent being the σύζυγος).  The phrase ἡ σύζυγος is well attested to mean wife, so it is not hard to see how Clement could have taken the passage to likewise mean wife from the grammar alone.  Additionally, the context of 4:2 where Paul greets two other women and asks (in 4:3) another person to counsel them makes a woman a possible target of "true companion" (the grammar is ambiguous as the word has the same form for masculine and feminine cases).

While the quote of Clement doesn't make his source clear, there is another extant commentary that makes the reference to Phil 4:3 explicit.  In his commentary on Romans, Origen (185-254) writes:


  Paul, then, if certain traditions are true, was called while in possession of a wife, concerning whom he writes in Philippians "I ask you also, my loyal mate, help these women."


Source: A Greek-English Lexicon of the New Testament and Other Early Christian Literature, Third edition