Where did the "theology" behind the Cherry tree carol come from? I love playing this carol on the piano, but it makes me wonder if I'm not being the least bit heterodox. 

Here are the assumptions that seem to me to be contrary to thriving tradition:



  When Joseph was an old man, an old man was he



Why is St. Joseph old in this carol?



  He married Virgin Mary, the Queen of Galilee



Why is Our Lady the Queen of Galilee? *



  There were cherries and berries, as thick as might be seen



Do they even have cherry trees in the Holy Land?



  Then Joseph flew in anger, in anger flew he,
  Let the father of the baby gather cherries for thee!



When did St. Joseph get a snarky and angry attitude?



  ‘And upon a Wednesday my vow I will make, 



I thought it was a Thursday (at least recognized as such in the west), is the carol saying that the Passion started on Wednesday?

I did a little bit of research on the wikipedia and the googles but it's still a bit lacking, apparently there are 4 versions of this carol (the version quoted here comes from Wikisource).  

* (not that I don't think the Queen of the Universe is also the Queen of Galilee)
The Cherry Tree Carol is thought to date to the 16th or 17th century.  The history of its development is murky, but it may be traced to a 15th century Coventry play1 and beyond that to the Gospel of Pseudo-Matthew, a 7th century apocryphal work describing the birth and childhood of Jesus.
The Gospel of Pseudo-Matthew, which titles itself The Birth of the Blessed Mary and the Infancy of the Saviour, was &quot;enormously successful&quot; as a text, in the words of scholar Mary Clayton, citing its high number (135) of manuscripts.2  Old English translations of it exist, dating to the 11th century or possibly earlier.3 So we see that Pseudo-Matthew's gospel was available to early English speakers well before the appearance of the carol.
Turning now to your points, we can see the correspondence:
Joseph was an old man: In Pseudo-Matthew's gospel, Joseph is a grandfather who is selected by his peers to be the guardian of the 14-year-old Mary:

Thou hast been made blessed in thine old age, O father Joseph, seeing that God hath shown thee to be fit to receive Mary. And the priests having said to him, Take her, because of all the tribe of Judah thou alone hast been chosen by God; Joseph began bashfully to address them, saying: I am an old man, and have children; why do you hand over to me this infant, who is younger than my grandsons?

The Queen of Galilee: This exact phrase is not used in Pseudo-Matthew's gospel, but Mary's companions in Galilee derisively apply the title &quot;queen&quot; to her:

Since thou art the last, and humble, and younger than all, thou hast deserved to receive and obtain the purple. And thus saying, as it were in words of annoyance, they began to call her queen of virgins.

Cherry Tree: Pseudo-Matthew does not refer to cherries in his work, but he does tell of an episode very similar to the one in the song.  Joseph and Mary, with the infant Jesus, are traveling through the desert on their way to Egypt.  Mary sees not a cherry tree but a palm tree (presumably a date palm) bearing fruit:

Date palms do not grow in the English-speaking countries of the 16th century, so a different tree was needed for the song, and the resemblance between dates and cherries is perhaps not far-fetched.
Hungry, Mary says to Joseph:

I wish it were possible to get some of the fruit of this palm.

Joseph's anger: Pseudo-Matthew doesn't portray Joseph as poorly as the song, but the connection is clear.  Joseph responds to Mary, saying:

I wonder that thou sayest this, when thou seest how high the palm tree is; and that thou thinkest of eating of its fruit. I am thinking more of the want of water, because the skins are now empty, and we have none wherewith to refresh ourselves and our cattle.

So Joseph refuses her, choosing instead to focus on collecting water.  However, the infant Jesus then takes matters into his own hands:

Then the child Jesus, with a joyful countenance, reposing in the bosom of His mother, said to the palm: O tree, bend thy branches, and refresh my mother with thy fruit. And immediately at these words the palm bent its top down to the very feet of the blessed Mary; and they gathered from it fruit, with which they were all refreshed.

Wednesday: Of the things you mention, the reference to Wednesday is the most difficult to connect directly to Pseudo-Matthew.  It only appears in one of the four versions of the carol.  Perhaps it is nothing more than a mistaken reference to the &quot;third day&quot; (a repeated theme in Pseudo-Matthew's gospel), a reference to Ash Wednesday (since Christians make &quot;vows&quot; for Lent), or a reference to Holy Wednesday, on which Jesus predicted his death (Matthew 26:6–12).
Theology
The Gospel of Pseudo-Matthew is one of several infancy gospels that attempt to &quot;fill in&quot; the details of the childhood of Jesus.  It derives much of its content from two earlier works, the Gospel of James and the Infancy Gospel of Thomas, though the source of the &quot;flight to Egypt&quot; portion is not known.
Pseudo-Matthew's story emphasizes the relationship between Mary and Jesus, to the relative exclusion of Joseph.  It also portrays Jesus as performing many dramatic miracles as a child, including the pacification of dragons who threaten the family in Egypt.  Not surprisingly, the story was very popular in the Middle Ages.
As far as serious theology goes, the Gospel of Pseudo-Matthew, and, by extension, the Cherry Tree Carol, doesn't contribute much.  But its origins are most likely found in popular curiosity and speculation about the childhood of Jesus.

See The Origins of Christmas, pages 58–60 for a general treatment of the gospel, carol, and the connection between them.  Mary Clayton's The Apocryphal Gospels of Mary in Anglo-Saxon England goes into significant detail on the origins of Pseudo-Matthew's gospel, particularly into Old English.

Samuel Burdett Hemingway, English Nativity Plays, page 257.  Coventry Nativity (IV) is shown to be based on Pseudo-Matthew and find a parallel in the carol.  The text for this play is dated to 1468 (page ii).
Clayton, page 18
Clayton, page 138