Toponymy:  Sussex
Suth Seaxe (late 9th century)    Sudsexe (1086)

I was not quite sure where to start looking.

Notes from Ency. Britannica:  Old English Suð Seaxe, South Saxons

Notes from my own past research:

In the Gallic Chronicle of 452, Tyro had written that the Britons in 443 were reduced "in dicionen Saxonum" (under the jurisdiction of the English). He used the Roman term Saxons for all the English-speaking peoples resident in Britain: it comes from the Welsh appellation Saeson ). The Roman historians had been using the term to describe all the continental folk who had been directing their activities towards the eastern and southern coasts of Britain from as early as the 3rd Century. By the mid 6th Century, these peoples were calling themselves Angles and Frisians , and not Saxons.

from

http://www.britannia.com/history/nararthist.html

The prefix south may have been added after  AD 477

Not by the Romans, but by the British or the German rulers? or in the Anglo Saxon Chronicle?

A.D. 449.  This year Marcian and Valentinian assumed the empire,
and reigned seven winters.  In their days Hengest and Horsa,
invited by Wurtgern, king of the Britons to his assistance,
landed in Britain in a place that is called Ipwinesfleet; first
of all to support the Britons, but they afterwards fought against
them.  The king directed them to fight against the Picts; and
they did so; and obtained the victory wheresoever they came.
They then sent to the Angles, and desired them to send more
assistance.  They described the worthlessness of the Britons, and
the richness of the land.  They then sent them greater support.
Then came the men from three powers of Germany; the Old Saxons,
the Angles, and the Jutes.  From the Jutes are descended the men
of Kent, the Wightwarians (that is, the tribe that now dwelleth
in the Isle of Wight), and that kindred in Wessex that men yet
call the kindred of the Jutes.  From the Old Saxons came the
people of Essex and Sussex and Wessex.  From Anglia, which has
ever since remained waste between the Jutes and the Saxons, came
the East Angles, the Middle Angles, the Mercians, and all of
those north of the Humber.  Their leaders were two brothers,
Hengest and Horsa; who were the sons of Wihtgils; Wihtgils was
the son of Witta, Witta of Wecta, Wecta of Woden.  From this
Woden arose all our royal kindred, and that of the Southumbrians
also.
 

The Gallic Chronicle

The Chronicle of 452
HONORIUS XVI (410)
Britanniae Saxonum incursione devastatae.
(The British provinces were devastated by an incursion of the Saxons.)
THEODOSIUS II XVIII/XVIIII (441)
Britanniae, usque ad hoc tempus variis cladibus eventibusque latae in dicionem Saxon rediguntur. Alani, quibus terrae Galliae...
(The British provinces, which to this time had suffered various defeats and misfortunes, are reduced to Saxon rule.)
The Chronicle of 511
THEODOSIUS II XVI (441)
Britanniae a Romanis amissae in dicionem Saxonum cedunt.
(Britain abandoned by the Romans passed into the power of the Saxons.)
----------------------------------------------------------------------------
The entries in the above Chronicles leave the impression that the Saxons had taken full control of Britain by the year 441. This was not the case, although it may have appeared so at the time. Perhaps the statements were made retrospectively and phrased the way they were to indicate that Vortigern had fallen under the influence of the Saxons by this time and that the whole island would surely follow.

http://www.britannia.com/history/bb441.html
 

During the late 200s and the 300s AD, the Romans established forts in Britain along the Litus Saxonicum, or the Saxon Shore. Their use of the term Saxon in this case included all sea-faring Germanic pirates, not a specific Germanic tribe. Hundreds of years later the term Viking was used in the same sense and included not only Danes, but Norwegians and Swedes as well.
http://www.geocities.com/farthegn/page33.html

Was the first official South Saxon reference the Domesday Book: under enquiry?