The external border of the Roman empire tended to be marked more or less with various defense systems and natural features like the Rhine and Danube rivers in Europe.
The defense features included military roads more or less along the frontier, forts, guard posts, customs posts at border crossings, palisades, earthen dykes, and stone walls. Thus it was often very easy to tell when you were entering or leaving the Roman Empire as a whole.
With the conquest of Italy, prepared viae were extended from Rome and its vicinity to outlying municipalities, sometimes overlying earlier roads. Building viae was a military responsibility and thus came under the jurisdiction of a consul. The process had a military name, viam munire, as though the via were a fortification. Municipalities, however, were responsible for their own roads, which the Romans called viae vicinales. The beauty and grandeur of the roads might tempt us to believe that any Roman citizen could use them for free, but this was not the case. Tolls abounded, especially at bridges. Often they were collected at the city gate. Freight costs were made heavier still by import and export taxes. These were only the charges for using the roads. Costs of services on the journey went up from there.
To combat the activities of thieves and highwaymen, most Roman roads were patrolled by special detachments of imperial army troops known as “stationarii” and “beneficiarii.” These soldiers manned police posts and watchtowers in both high traffic and remote areas to help guide vulnerable travelers, relay messages and keep an eye out for runaway slaves. They also doubled as toll collectors. Like modern highways, Roman roads were not always free of charge, and troops were often waiting to levy fees or taxes on goods whenever the route reached a bridge, mountain pass or provincial border.
The Romans also used to levy such duties as state and provincial or city taxes. As early back as the Roman times customs duties made up a significant part of public revenues for the state treasury. At certain communication points in the provinces there were customs stations (stationes) where the duties were charged for the goods passing such points. The amount of duties was 2.5% (quadrogesimo) of the value of imported goods. The collection of customs duties was also farmed out, at the beginning granted even to farmers from the ranks of domiciled population, and later on, from mid-2nd century on, duties were collected by officials that in our territory were called publicum portarii Illyrici et ripae Thraciae.
Internal customs in the Roman Empire1
So if internal customs duties were sometimes charged, and tolls for using the roads, travelers could ask or be told what province or dioceses or prefecture they were in, and which side of the empire it belonged to. Government offices and public buildings - possibly including toll collection posts - usually had portraits of the emperor or emperors. And possibly the eastern emperor was always more prominent in the eastern empire and vice versa.
From the maps I have seen, the border between the eastern and western empires in Africa was in modern Libya, between Sirte and Benghazi, and probably near Bin Jawad, As Sidr, or Ras Lanuf. The province of Tripolitania would have been in the western empire, and Cyrenica - the province of Lybia Superior - in the eastern empire. I don't know how visible the border between east and west was in Africa.
In Europe the border between the eastern and western parts of the empire was much longer. In the south, the province of Dalmatia was in the western part, and the province of Praevalitana was in the eastern part. To the north, Dalmatia was in the western part of the empire and Moesia I was in the eastern part. Part of the Province of Pannonia II in the west was north of part of Moesia I.
The Sava River was the border between Pannonia II in the north and Moesia I in the South. The Drina River that zig zags north to join the Sava River was partially the border between Dalmatia and Moesia I. Today it is part of the border between Bosnia and Herzegovna and Serbia. The border was roughly north and south from somewhere on the Drina River to the Adriadic Sea somewhere near Budva. Most of modern Montenegro was east of the border.
So much of the border in Europe was made by rivers. Crossing those sections of the Save and Drina rivers meant crossing from one half of the empire to the other. And travelers probably had to pay tolls and sometimes tariffs on their merchandise when crossing the border.
And as far as I know that would have been all the formalities involved.