Originally, NT texts were written without spaces or any explicit indicator of word division. Such writing is known as scriptio continua. On page 31 of Manuscripts of the Greek Bible, Professor Bruce Metzger says, "Occasionally the grouping of syllables into words is ambiguous. ... It must not be thought, however, that such ambiguities occur frequently. In Greek it is the rule, with very few exceptions, that native Greek words can terminate only in a vowel (or dipthong) or in one of three consonants." So translators could for the most part tell when words began and ended. Wikipedia claims without a source that, "By around AD 1000, European texts were written with spaces between words." My gut is that this somewhat unhelpful figure is basically true, but I wouldn't put it in a paper or anything unless I located a source.
Sentences and paragraphs
In a 2006 article ("Chapters, Verses, Punctuation, Spelling, and Italics in the King James Version") in the BYU publication The Religious Educator, it says that paragraph divisions originated in the fifth century:
New Testament Paragraphs
As with the Old Testament, we do not have any original New Testament texts. But we do have very early textual evidence of the New Testament from the beginning of the second century, and those earliest manuscripts were written in the tradition of Greek texts of their day, in all capital letters, with no division between the words or sections. Although the modern reader may be bewildered by a text that has no apparent breaks, the ancient Greek has a set of rhetorical particles that indicate natural pauses and breaks in the text. Most New Testament texts were written on parchment or papyrus, and by the second century, they began to be written in codices (books with leaves bound together—singular, codex) rather than on scrolls.
Just as in the Hebrew tradition, the first system of division in the New Testament text was the paragraph, which naturally followed the rhetorical and grammatical particles in the text. One of the earliest systems of division in the New Testament is attested in the Greek Bible manuscript Vaticanus, dating from the fifth century AD. In Vaticanus, the scribes used a system of unknown origin in which the text was divided into sections corresponding to the break in sense. Those divisions were called in Greek kephalaia, which means “heads” or “principals.” They were named and numbered in the margins and are the first attested form of a sort of chapter division in the New Testament. In Vaticanus, for example, the Gospel of Matthew was divided into 170 such units—62 in Mark, 152 in Luke, and 50 in John. The kephalaia were much smaller in length than the present-day chapters and are much closer to the paragraphs. In other Greek manuscripts, Acts, the Epistles, and Revelation were similarly divided into chapters and smaller sections.
As they did with the Old Testament, the King James translators indicated paragraph divisions in the New Testament with paragraph markers ( ¶ ). Often, but not always, their paragraph divisions coincide with ancient kephalaia and chapter divisions known from early manuscripts, but for some reason that mystifies scholars to the present day, they end at Acts 20:36.
At the same time the kephalaia divisions in the New Testament were being made, rudimentary smaller divisions, indicated by simple forms of punctuation (sixth through eighth centuries), were beginning to be marked in the Greek texts; these divisions would eventually be reflected in the chapter and verse divisions after the thirteenth century.