The Saxons probably moved in in force in the fifth century AD when the Romans withdrew.
I studied this period of English history at University and have since taken courses in Old English (language of the Anglo-Saxons). General view appears to be that when the Romans arrived Britain was populated by tribes speaking Celtic languages, ancestral to Welsh or the extinct Pictish. However, the Romans were not interested in recording the languages their barbarian subjects spoke and it is conceivable there were enclaves speaking other language(s).
The earliest (doubtful) reference to Saxons under that name is in Ptolemy's geography Second Century AD, as a tribe in Continental Europe. By late Roman times fierce pagan Saxons were recorded raiding Britain and northern Gaul by sea, and there is some archaeological evidence that (as with other Germanic tribes) some Saxons joined the Roman army and served in Britain.
After the Romans abandoned Britain in the early fifth century AD we have little record of what happened there. By the end of the sixth century, when they began to adopt Christianity and leave significant written records the Saxons and closely-related Angles and Jutes were established occupying most of what is now England, Celtic speakers remaining independent in the poorer, more mountainous territories in what are now Scotland, Wales and Cornwall. Saxons, Angles (and the less common Jutes) were sufficiently similar in speech and culture that they quite quickly blended into an Anglo-Saxon/ English nation, and the terms Saxon and Engel (Angle or English) were used almost interchangeably.
Apart from Bede, whom you mention, whose Eighth Century Ecclesiastical History of the English People treats Saxons, Angles and Jutes as one people, other sources include:
-'The Ruin of Britain' by Gildas, a British/Welsh monk writing in Latin in the fifth century who regards the conquest of much of Britain by the Anglo-Saxons as God's punishment for the Britons' gluttony, drunkenness and other sins.
-The Anglo-Saxon Chronicle in Old English and giving an English point of view probably compiled by order of King Alfred the Great in the late Ninth Century, from poems and other traditions and sources we do not know.
-Mention by continental writers. They say so little about Britain for a few hundred years after the Romans left that its contacts with the civilized world must have been severely curtailed following the pagan Anglo-Saxon conquest but there are a few mentions
-Archaeology, although we have to be careful that in the absence of written records we do not necessarily know if e.g. a change in farming or burial practice means a new population coming in or what language they spoke.