Most likely Greek. This is the only language which we know they definitely had in common, and both were highly proficient in it.
High-born Romans learnt Greek and Julius Caesar was no exception:
According to the 1st century C.E. Roman historian Suetonius, Julius
Caesar spoke mainly Greek and not Latin, as was the case with most
patricians at the time.
Richard A. Billows, Professor of Greek and Roman History at Columbia
University in New York, elaborates on Caesar's education:
The formal side of his education consisted of being taught to read and
write both Latin and Greek, given a grounding in the classic poets of
Rome (Ennius, Naevius, Terence and others) and Greece (Homer, some of
the lyric poets, the Athenian dramatists and others), and then taught
a smattering of Greek philosophy, but above all the art of rhetoric.
Source: Richard A. Billows, 'Julius Caesar: The Colossus of Rome' (2009)
Cleopatra, being of the Ptolemaic dynasty of Egypt, spoke Greek:
Most historians agree that Cleopatra did not speak Latin and that she
spoke Greek, which was her native language. The historian Plutarch was
not convinced that she actually did speak Egyptian, and many modern
scholars agree with him. Some languages that she may have spoken were
Persian, Syrian and Arabic. However, there is no true historical proof
that she spoke anything other than Greek.
Plutarch also mentions Ethiopian, Trogodyte, Hebraioi, Parthian and others not specified. One of the latter may have been Latin but we can only speculate on that as,
Plutarch is our only ancient source for Cleopatra’s knowledge of these
languages. Note that Latin is not included in the list. It is possible
that Latin was one of the many other languages with which Plutarch
credits Cleopatra, but Julius Caesar and Mark Antony spoke Greek, so
communication would not have been a problem.
Source: Prudence J. Jones, 'Cleopatra: a Sourcebook' (2006)
Duane W. Roller, Professor of Classics, is more open to the idea that Cleopatra spoke Latin but nonetheless concurs that she would have spoken Greek with Julius Caesar and other Romans.
A Note on Plutarch's use of Arabic
Although somewhat off-topic in relation to the question, the mention of Arabic has generated a fair amount of discussion in the comments. This is evident in the academic literature:
The meaning of the term ‘Arab’ in antiquity has been hotly debated for
many decades. One reason for this has been the search for a single
definition which could be applied to all the numerous references to
‘Arabs’ and ‘Arabias’ in the ancient sources. As noted above, the vast
majority of these sources were written by authors looking at the
ancient Near East from the outside.
Source: G. Fisher (ed), 'Arabs and Empires before Islam' (2015)
Plutarch's reference probably relates to one of the languages spoken on Arabian peninsula, possibly Nabataean Arabic. Modern scholarship postulates that the spoken form probably predates the written form by several centuries, perhaps as early as the 4th century BC. Consequently, Arab speakers
used other languages for writing, principally Nabataean Aramaic in the
north of the Peninsula, and Sabaʾic in the south. Thus an Arabic
speaker would either learn the language and script of Aramaic or
Sabaic in order to be able to write, or employ someone to write, in
these languages for him/her.
On the importance of Nabataea to Egypt,
Across the Red Sea was the Arabian peninsula. Although only small
parts of it were ever under Ptolemaic control, this region was a vital
part of the Ptolemaic kingdom’s economy. The great Nabataean trading
center of Petra began to flourish in the late fourth century b.c., and
a certain Anaxikrates explored the Red Sea for Alexander, reaching the
wealthy aromatics-producing regions at its southern end. By the third
century b.c. the trade route from Petra to these districts was well
known, and frankincense and myrrh, the two most famous aromatics, were
exported to processing factories in Alexandria. Knowing the Arabian
language may have assisted Cleopatra in diplomatic and mercantile
negotiations, and she may have acquired some Arabian territory in the