The order of magnitude is about 50 miles, or 80 km.
The Pauline Baynes' annotated map, as linked by Edlothiad, was based on one of the maps included in the novels, and its printed form was not meant to be extremely large; because of this, it is depicted in a somewhat small scale, where its details are large and out-of-scale, meant to be easily visible and identifiable1.
Also, the purpose of the map was not only strictly geographical but also had a somewhat artistic role, the emphasis is put more in quality than quantity, and it is meant to resemble more cartography from the Middle Ages rather than modern one, as in Tolkien's times.
Despite of this, it is still an official map from the author himself and should be taken into account.
Given this premise, a rough estimation can be done, and by measuring we can find that the two cities are depicted as being about 60 miles apart:
On another source, Karen Wynn Fonstad's Atlas of Middle-earth, in itself an unofficial but generally well respected source, the two cities are distant more or less 45 miles from each other.
The maps in the Atlas are depicted on a larger scale than the official ones like those on the various novels, and because of this distances could be measured a bit easier.
Also, they are drawn in a more modern way, putting more attention in the actual geographical and geological features rather than a pretty artistic depiction of all the objects (cities are shown as simple dots).
But it is not an official source, and the depiction is based on Fonstad's reasonings and speculations, that even if often reasonable and convincing, are not from Tolkien himself.
Anyway, the map of Mordor and its surroundings clearly shows the relative position of the two cities:
A detail of the area discussed here, with the mile scale put in place:
The distances here are a bit different from the official map, but they are more or less in the same order of magnitude: the official, less detailed, map gives about 60 miles, while the unofficial, but more detailed one, shows about 45 miles. These values are a bit different, but if we don't need an exact figure and we can content about an estimation, we can approximate by saying that they are more or less 50 miles, or 80 km, apart.
1. In example, Minas Tirith and Minas Morgul are shown as "cones" with a respective width and height of about 5 and 10 miles (clearly not the real size of these cities).