Great question that I haven't really given thought previously! I looked into the sources and scholarship on this and it's actually quite interesting, and it’s worth having first a short excursus to the history of kneeling before authorities in the Greek world.

Classical Greeks considered prostrating before a king an exclusively Eastern custom; Herodotus and Xenophon talk a lot about this and for them, it's sort of a symbol of the servile and soft nature of the Persians. Proskynesis (προσκύνησις) is the Greek technical term for it, and it comes from the verb proskynein (προσκυνεῖν) which actually means 'greet', 'welcome respectfully', or 'kiss' (which the Greeks often did upon meeting). When it's used in the context of coming face to face with gods in temples etc., it in turn means to 'make obeisance' and 'fall down and worship'. However, when discussing proskynesis by Persians in front of their kings it is very clear that it is the latter sort of, full prostration and submission before a king; the Classical Greeks found the custom wholly unacceptable, a gesture that should be reserved only for the relationships with the gods. According to Xenophon, the Greeks living in Asia Minor (modern Turkey) around 400 BC had been forced to bow down to their Persian masters. The Spartan king Agesilaus’ campaigns in the East put an end to this (Xenophon, Agesilaus 1.34). However, Greek ambassadors to the Persian king were still expected to bow down in front of him, and Cornelius Nepos, a Roman Republican writer of the 1st century BC, tells an anecdote where the Athenian general Conon chose to send a letter to the Persian king instead so that he wouldn’t have to go through such an humiliating affair (Conon, 3.3-4).

Which gets us to the Roman ideas of prostrating, which where very similar than in the Greek world; the Latin words that are more or less synonymous with proskynesis are (se) prosternere (‘to prostrate oneself to show obedience’), used often in Roman text when individuals (desperately) beseech someone of upper status for something (slaves falling down and embracing the knees of their masters etc.), or adorare, which is similarly a show of obeisance but more often used in the context of worship of divines. So, there was of course no monarchs in Republican Rome and expecting something like this from one’s subordinates would have been severely out of place, but did the Roman emperors expect their subjects to do this in front of them like Persian kings?

We know that it became a staple practise during the late Roman Empire; Diocletian is often credited with starting the expectation of a proskynesis in imperial court. Ammenius Marcellinus (4th century AD; 15.5.18) remarks on this; he says that Diocletian (emperor AD 284 to 305) was the first Roman emperor who let himself be venerated with the ‘barbarous ritual and royal fashion’ of the proskynesis, when the emperors before him had been happy to be simply saluted 'like judges' (whatever that means). It’s not quite clear whether Diocletian truly started to demand proskynesis from his subjects, but we do know that proskynesis became a standard, elaborate ritual of the imperial Byzantine court - Procopius says (Historia arcana 30.24) that at the time of Justinian (emperor 527 to 565) all those who were admitted to the presence of the emperor fell on their faces on the floor, stretching out their hands and feet, kissed the Emperor’s feet and then stepped back to continue whatever business they had with the Emperor. Stanislav Doležal thinks that the proskynesis was not a complete Late Antique invention, and sites several cases where earlier emperors also received the semi-ritual proskynesis; but, all the cases to me seems rather special occasions, where somebody recognises the authority of a new emperor for the first time or when a foreign leader submits to the Roman emperor (in art, too; see e.g. the panel of Marcus Aurelius where the ‘barbarians’ prostate themselves before the emperor, so I think it might be rather safe to give some credence to Ammenius Marcellinius words: kneeling or bowing down before the Roman emperor was not the normal way to greet the emperor during the early and high empire; proskynesis was reserved for special occasions, and usually performed only from the subject’s own initiative rather than something expected by the emperor as ‘normal’ behaviour on day-to-day meetings.

How did someone then act in the presence of an Roman emperor before late antiquity, then? What sort of could the ‘normal greeting’ referred to by Ammenius Marcellinius could have been like? In the movies, of course, Roman do the ‘Roman salutation’ of saying ‘ave’ and lifting up their right arm, but this is actually a modern misconception - there is no contemporary sources whatsoever that would suggest this was a normal way to greet someone of authority. Sometimes, Romans might lift their hand to the emperor when in the process of performing an acclamatio, a public, semi-ritualised expression of reverance and love to the emperor, such as we can see the audience doing in Trajan’s column when Trajan returns triumphantly to Rome. So, this was not something one would do habitually when coming to meet the emperor one-to-one. Most likely there was no special rule how to greet the Roman emperor; probably just polite verbal salutation, or, if even somewhat close to emperor, we might imagine the emperor and subject embracing or kissing each other (all high-ranking Romans with any links to the emperor were formally considered as ’friends with the emperor’, even though the relationship was pure business).

This is not to say that body language and gestures weren’t important for up keeping relations of authority and reverence; in fact, they were very important. The ancient Rome was of course a strictly hierarchical society and all individuals were expected to conform to the proper norms and demonstrate compliancy to these social hierarchies. Covering one’s head was a common way to show reverence and submission before someone of superior status (also when ‘conversing’ with the gods through ritual). Sitting and standing up were perhaps the most important and immediate way to show respect to whoever was higher up in the ladder (see Glenys Davies’ interesting article on sitting and authority in Greco-Roman art in that Douglas Cairns edited collection below). Different ‘special’ chairs of a judge, consul, emperor etc. in themselves were hugely important status symbols in Ancient Rome. It was a normal custom in the imperial Senate that, whenever a magistrate stood up to speak, all the senators who were his junior should also stand up as a show of respect. Pliny the Younger in the Panegyricus (64.2-4) is absolutely shocked by the insolence of a ruling consul who did not stand up when the emperor (Trajan) himself in the senate stood up to speak - everyone should be standing, since there possibly cannot be anyone who isn’t the emperor’s junior in the room. To sit down when others are standing is thus a symbol of high status and authority. So, in Roman art, the authority of the emperor is often represented simply by showing the emperor seated when everyone else is standing; such as in this and this stone panel, originally part of Marcus Aurelius' triumphal arch and reused in late antiquity in Constantine’s arch.

TL;DR: Kneeling or bowing down was not the standard way to greet the Roman emperor during the early and high empire. Simply things such as standing in front of a seated emperor were enough to denote the status differences. However, sometime in late antiquity it seems the ritual of proskynesis - falling at the feet of a king - which the Greeks and Romans considered an Eastern (and barbaric) tradition comes a standard part of imperial court life.

Further reading: Some remarks on the origin of ΠΡΟΣΚΥΝΗΣΙΣ at the Late Antique imperial court, Stanislav Doležal, Byzantion, Vol. 79 (2009), pp. 136-149.
Nature Embodied: Gesture in Ancient Rome, 2004, Anthony Corbeill.
Body Language in the Greek and Roman Worlds, 2005, (ed.) Douglas Cairns.

Follow up question, if they did kneel, when did the practice originate? Are there earlier Roman precedents or would it have been something new?

Follow-up question: Were barbarian ambassadors and representatives (pre-Diocletian) expected to bow, kneel or perform proskynesis?