How does each robot decide whether to stay put or not if it can't communicate with the other?

Ha, good point. Could be pre-arranged. But if something can be pre-arranged, I like mikeash's answer.

Most of them have means to leave marks on the ground. Would that count as communicating for that exercise?

That might work on the moon, but on Mars... http://www.universetoday.com/14892/mars-dust-storms/

>> Because the planet’s atmosphere is only about 1% as dense as Earth’s only the smallest dust grains hang in the air.

It should be possible to move a few larger rocks, maybe? Spirit, Opportunity and Curiosity have robotic arms. Good image processing might or might not recognize patterns in the stones.

(http://nssdc.gsfc.nasa.gov/image/planetary/mars/vikinglander... for an example what most images I saw look like. I imagine it looks like this after a storm: http://nssdc.gsfc.nasa.gov/image/planetary/mars/vikinglander...)

(Of course, compared to mikeash's answer, this is overengineering and only applicable if their conditions are not met (prearranged meeting point; we have a map and know our location))