The Golden Legend by Jacob de Voragine has several different origin stories for the wood of the Cross. In one, the Cross was made from the wood of three trees which grew from three seeds that had been planted by Seth in the mouth of his father's, Adam's, corpse. Seth had taken the seeds from the "Tree of Mercy" (which is not part of the Biblical story).
Another version related by Voragine explains that the wood came from a cutting from the Tree of Knowledge of Good and Evil, also planted by Seth on Adam's grave.
From either of these origins, an elaborate provenance was created to get the wood from Eden to Golgotha. The wood was made into the rod of Moses, which was planted by King David in Jerusalem, from which grew a tree that enabled Solomon to carve a beam for his temple. Eventually, the tree was cut down for wood that was used to build a bridge used by the Queen of Sheba to visit Solomon. The Queen had a vision that a piece of wood from the bridge would lead to the replacing of God's covenant with the Jews (this would be Jesus and his message). Solomon, thinking this a tragedy, had the wood buried. It was exhumed years later and some was used to make the True Cross.
How did it come to be discovered after the crucifixion? For that, we must talk about a remarkable woman, the Empress Helena of Constantinople, which we will do next.