Did the early church believe that Jesus was crucified on a cross or on a stake?

Perhaps I don't answer your specific question very well, but three early indications our Lord was crucified on a cross can be added to other early evidences:-

The Alexamenos Graffito shows a man with a donkey's head being crucified on a cross. This griffiti on a plaster wall was found in Rome. Because the accusation that Jews and Christians worshipped a donkey's head is refuted as early as Josephus (AD 38-100) and Tacitus (AD 56-120), it is supposed this graffiti was equally early. The Greek writing says "Alexamenos worships his god".

Secondly, Jehovah's Witness pictures of the crucifixion typically show one nail thrust through both wrists/hands. But in John 20:25 we have the declaration of the apostle Thomas "unless I see in his hands the print of the nails..I will not believe". He said "nails" not "nail". Thomas clearly believed there was more than one nail put through our Lords hands.

Thirdly, there are the ossuaries. An ossuary is a bone box containing the bones of the deceased. They were commonly used from the time of Herod until the destruction of Judaea in AD 70. It is believed they continued in use until AD 135. At the end of the nineteenth century Charles Clermont-Ganneau found many ossuaries in Judaea especially Jerusalem with a cross symbol inscribed on the outside together with the name of the deceased. He believed they were evidence the dead person was a Christian. For instance, see https://www.tandfonline.com/doi/abs/10.1179/peq.1974.106.1.53?journalCode=ypeq20 and https://archive.org/details/archaeologicalre01cler/page/352/mode/2up and succeeding pages.

Further to the last point in an answer here, there is more information that can be used to show how the early Christian Church viewed the implement of Christ's death.

Although not written in the era of the early Church Fathers, there is a book by Justus Lipsius called "De Cruce Liber Primus" On page 1155, there is a depiction of a man hung to die on an upright pole. Lipsius calls this the Crux simplex. Very good. Nobody has ever said the Romans did not crucify people that way.

Source : http://commons.wikimedia.org/wiki/File:Justus_Lipsius_Crux_Simplex_1629.jpg but then go to page 661!

However, there is another illustration in the same book, on page 661, with a man crucified on a complex cross - one that has a cross-piece near the top - so, both arms are stretched out to the side of the victim, one nail in each. Lipsius describes the cross as having four pieces (upright beam, crossbar, block below for the feet to rest on, and an inscription.) He speaks of Iraneus, circa AD 177, describing Jesus' cross to be like that, as does Tertullian, a little later.

Some protest that God would not allow his Son to be killed on a pagan instrument of torture. Yet the point about the cross being pagan is utterly irrelevant, because the Romans were pagans! Of course they used pagan instruments of torture! That was only to be expected!

It is true, however, that the Greek word 'stauros' can, indeed, refer to a single stake or pole, but please note that that is a Classical Greek word. Yet the Bible was not written in Classical Greek. It was written in the common, koine, Greek of that era. And, back then, the Romans frequently used cross-pieces on their crosses as well as their crux simplex. They had other variations on that theme too.

Finally, the early Christian Church knew that the Bible warns that the cross of Christ is offensive to most people (1 Corinthians 1:18 & Galatians 5:11). We know that today, as well, which gives rise to the question, Why would anyone claiming to be Christian object vehemently to the design of the instrument of torture used to overcome sin, death and the devil? The whole point about the death of Christ hinges on who it was who hung there, and why. Debating the shape of the instrument of torture totally detracts from the immensity of what Christ's death amounted to by way of his agonizing suffering for sinners, and how it achieved salvation for repentant sinners trusting in that awesome provision.

EDIT – In response to a request for more information on the Greek word ‘stauros’ as used in Classical Greek, I make the following quotation from a source that calls upon Classical Greek usage to support taking ‘cross’ to mean a simple, upright stake or pole, and not a complex stake or pole:

“In the classical Greek the word stauros meant merely an upright stake or pale, or a pile such as is used for a foundation. The verb stauroo meant to fence with pales, to form a stockade or palisade… the popular Greek hero Prometheus was represented as tied to a stake or stauros. The Greek word which the dramatist Aeschylus used to describe this means to fasten or fix on a pole or stake, to impale, and the Greek author Lucian used anastauroo as a synonym for that word.” The Kingdom Interlinear Translation of the Greek Scriptures, p1155, 1969 edition.

It then goes on to argue from silence that this must also be the sense in which writers of New Testament Greek used the word stauros. Well, the problem with that is the time gaps involved, and the fact of language evolving over the centuries. Here is a quote from a secular, non-religious source re. the Greek language:

“Ancient Greek from the 14th to the 12th centuries B.C.; Archaic Greek until 800 B.C.; Hellenistic Greek, the common language of Greece, Asia Minor, W. Asia, and Egypt to the 4th century A.D.; and Byzantine Greek, used until the 15th century and still the ecclesiastical language of the Greek Orthodox Church… Hellenistic Greek was an important language not only in the Near East but also in the Roman Empire generally, and is the form also known as New Testament Greek.” The Hutchinson Encyclopedia, p365, 1991 edition

To call upon the Classical Greek meaning of a word 4 centuries before the New Testament was written as an argument for denying that the stauros of Christ could have been a complex cross is as absurd as claiming that the 4th century Middle English meaning of the English word ‘gay’ can be an argument (from silence) that modern-day use of that word only means mirth, a light-hearted, carefree, sportive disposition. That is why my second paragraph said what it did.

[1] What Jehovah’s Witnesses believe regarding the cross and what they call a torture stake:

Jehovah’s Witnesses believe that the Christian cross is a pagan symbol. In their Kingdom Interlinear Translation (KIT) of the Christian Greek Scriptures there is an appendix on Matthew 10:38, which is rendered "torture stake" in their New World Translation of the Christian Greek Scriptures (NWT). This appendix says the classical Greek word 'stauros' means an upright stake or pole. However classical Greek was not the original language used to write the New Testament gospels and letters. It was written in koine (common) Greek. Although the appendix notes this point, it then claims that the Christian writers used the word to mean the same as in the classical Greek but without offering any proof for this claim.

[2] From Koine Greek into Latin:

After the original writings in koine Greek, the New Testament was written in classical Greek, and from there into Latin, where 'crux' is the word used. Justus Lipsius's "De Cruce Liber Primus" has an illustration of a man hanging by hands over his head, on a straight pole. On page 661 the text quotes the words of Pope Innocent (401-17AD) on the matter:

In the Lord's cross there were four pieces of wood... (including the inscription).

Lipsius also quotes Iraneus (Bishop of Lyons in 177AD):

The construction itself of the cross has five ends, two on the vertical and two on the horizontal, and one in the middle where the person attached with nails rested.

Also on page 661 Lipsius has an illustration of a cross with a cross-beam and a foot-rest, upon which a man is nailed, arms outstretched. This is under the heading "De Cruce Liber Secundus".

[3] What the early Church Fathers believed:

Irenaeus (early 2nd century – AD 202) remarks that "the very form of the cross, too, has five extremities, two in length, two in breadth, and one in the middle, on which [last] the person rests who is fixed by the nails".

The same remark is made by Justin Martyr (100–165) when commenting on the Book of Deuteronomy 33:17: "No one could say or prove that the horns of a unicorn represent any other fact or figure than the type which portrays the cross. For the one beam is placed upright, from which the highest extremity is raised up into a horn, when the other beam is fitted on to it, and the ends appear on both sides as horns joined on to the one horn. And the part which is fixed in the centre, on which are suspended those who are crucified, also stands out like a horn; and it also looks like a horn conjoined and fixed with the other horns".

To the pagan jibe about Christians being devotees of the cross, Tertullian (c. 155 – c. 240) responds by saying the pagans no less adored images of wood, with the difference that they worship what is only part of a cross, while the Christians are credited with "an entire cross complete with a transverse beam and a projecting seat". He then adds that "the very structure of our body suggests the essential and primal outline of a cross. The head ascends to the peak, the spine stands upright, the shoulders traverse the spine. If you position a man with his arms outstretched, you shall have created the image of a cross."

Justin Martyr also states: "That [passover] lamb which was commanded to be wholly roasted was a symbol of the suffering of the cross which Christ would undergo. For the lamb, which is roasted, is roasted and dressed up in the form of the cross. For one spit is transfixed right through from the lower parts up to the head, and one across the back, to which are attached the legs of the lamb.

https://en.wikipedia.org/wiki/Descriptions_in_antiquity_of_the_execution_cross#Made_of_more_than_one_piece

Regardless, Tacitus, Josephus, the Talmud, and Lucian all mention that He was crucified as opposed to being nailed up on a single upright wooden pole. Tacitus and Josephus say the crucifixion of Jesus occurred under Pontius Pilate. The Talmud says it happened on the eve of Passover. Please refer to the answer given in this question: Is there any evidence of the crucifixion of Jesus outside of the bible?

I am sure there is more information to be found to show that the early Christians and Church Fathers understood that Jesus was nailed to a T shaped cross, and not a single upright pole. I hope this will suffice and that others may contribute additional sources.

EDIT: Please note that the Wikipedia article partially quoted in the answer posted by stkuser deals mainly with ancient Greek language and customs. But with the Romans and the Hellenistic period, changes were introduced.

After explaining how a transverse piece of wood was commonly added to an upright pole, Free Church of Scotland theologian Patrick Fairbairn makes this important point: ...about the period of the gospel age crucifixion was usually accomplished by suspending the criminal on a cross piece of wood. — Patrick Fairbairn, Imperial Bible Dictionary, 1866 https://en.wikipedia.org/wiki/Stauros#Interpretation