What is the distance between Tharsis Montes and Cydinia Mensae on Mars
in kilometers?

After obtaining the longitude/latitude of the two points, apply a
Great Circle Distance formula (look on Wikipedia).

It depends on what coordinate system you are refering to. 

   The planet's surface, on a large enough scale, tends to be
approximately spherical. So the surface is a spherical coordinate
system. But the planet is also embedded within a rectangular
coordinate system. For two points on the planet's surface, there is an
infinity of paths restricted to the spherical system between them. But
there is one, unique such path on the surface which is the shortest of
them all.

   But for those two same points there are infinitely many paths in
the rectangular system, with a unique, shortest path between them.
This path however is shorter than the shortest path on the surface.
The reason of course is that in rectangular coordinates the shortest
path reduces to a straight line segment, whereas on the surface the
shortest path is restricted to a curved segment, which necessarily is
longer, given the two end points.

   But, interestingly, if the two points are allowed to move towards
each other while still restricted to the surface, as the distance in
either coordinate system approaches zero, the ratio of the two lengths
approaches 1/1. So just an "instant" before the points merge, their
distances in both coordinate systems are equal.

I get 5719 km if you want to check your (and my!) calculations. (This
is about twice the Nashville to Los Angeles distance given in the
wikipedia example.)

Formula used: 

d=a cos-1 (cos del1 * cos del2 * cos (l1 - l2) + (sin del1 * sin del2))

which is Eq. 5 from 

http://mathworld.wolfram.com/GreatCircle.html

where del1 = latitude of point 1 and l1 = longitude of point 1, etc,
and a=Mars mean radius.

(This equation is also one of those shown in wikipedia.)

Data used is from 

http://nssdcftp.gsfc.nasa.gov/miscellaneous/planetary/viking/mars_gazetteer.txt

for latitude and longitude

Cydonia mensae: 37.00 12.80 (Note spelling difference)
Tharsis Montes : 2.80 113.30

Average volumetric radius is from

http://64.233.179.104/search?q=cache:msInCnMtaCAJ:www.spds.nasa.gov/planetary/factsheet/marsfact.html+mars+radius&hl=en&gl=us&ct=clnk&cd=1&client=safari

3390 km

Check on calculations: first I set up a spreadsheet to calculate the
example distance for earth given in wikipedia, then substitued in the
values for the two points on Mars, so there should be a problem only
if I typed in the Mars values correctly. (Note: I ended up converting
degrees to radians; you could also use Excel functions like
COS(RADIANS(del1)) and use degrees directly.)

Search strategy;
1) "Tharsis Montes" "Cydinia Mensae" latitude longitude

corrected to
"Tharsis Montes" "Cydonia Mensae" latitude longitude
at Google's suggestion

2) mars radius

3) "great circle"

"so there should be a problem only
if I typed in the Mars values correctly"

should be

"so there should be a problem only
if I didn't type in the Mars values correctly"

Here's hoping you get the same result; I also learned something about
how Excel uses sin and arccos in the process.