The main idea here is just that it takes time for light to travel, which is the same thing as the Doppler shift (the longitudinal version which applies at all speeds, not the relativistic transverse one). Relativistic effects like time dilation (the moving clock ticks slower) and gravitational redshift (the clock at the bottom of Earth's gravity well ticks slower than the one in flight) cause small differences, but the travel time Doppler is still obvious even when the others are ignorable.
The clocks stay synchronized as they move apart. The only reason they appear to differ is that when one of them is far away, you're not seeing it in the present. You're seeing it as it was some time ago — and the farther away it is, the longer ago you're seeing it. When the clock traveling to Mars is one light-minute away, you're seeing it as it was one minute ago, because it took one minute for the image taken a minute ago to travel to you at the speed of light. When the Mars clock is two light-minutes away, you're seeing it as it was two minutes ago, and so on.
One light-minute is just under 18 million km. At a speed of 11 km/s, it takes about 19 days to get that far away. The moving clock appears to be ticking slower, at 99.9963% of the rate of the stationary clock, so it loses one minute every 19 days. The fractional change in frequency (1 part in 27,360) is just the ratio of velocities, because in time $t$ it moves $vt$ farther away, causing an additional signal travel time delay of $vt/c$. That's the Doppler shift.
As in Cadence's comment, this only happens on the way out. If the mission includes a return trip, the sign of the shift reverses. The traveling clock appears to be ticking slower when moving away, but when the relative velocity goes to zero, the two clocks tick at the same apparent speed, maintaining a constant offset. It doesn't stay zero for more than an instant, though. As in Paŭlo Ebermann's comment, since the planets have different velocities, the distance between them is constantly changing, with direction depending on what part of the orbital cycle we're in, so the moment of zero range rate is not in Mars orbit itself unless the timing gets extremely lucky. When the traveling clock turns around and heads back, it appears to be ticking faster, again by exactly the Doppler factor of $v/c$, so that it comes gradually back into synch when it arrives home. As in PM 2Ring's comment, any difference between the two clocks when they are brought back to the same position constitutes a measurement of relativistic effects due to the differing acceleration histories of the two clocks.
