If they can't communicate with each other, why would they want to meet?

Assuming Mars is featureless (if it has features, they can both climb Olympic mons, for instance, as Mike Ash already said) and they cannot leave Mars (if hey do, they could have agreed before to meet in a bar in, say, Paris), the solutions I can think of all are a bit impractical:

- both dig a hole to the center of Mars and wait there for the other to arrive.

- both spread themselves out over half the area of Mars.

- both self-replicate until they cover the surface.

- at least one of them starts annihilating Mars.

If they are allowed to discuss strategy beforehand, the following will work:

Both walk straight ahead along a great circle. When (not if; great circles cannot not intersect and not be the same) they meet the trail of the other, the slower one stops at the intersection, and waits for the faster one to return on its path.

It's easier to go to the North or South Pole, instead of the center of the planet, because you don't have to dig so much. As a guide you can use a gyrocompass that don't need a magnetic field for orientation: http://en.wikipedia.org/wiki/Gyrocompass IANARS

I'm guessing one stays put and the other does a grid pattern search.

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))

Start by solving the problem for two robots lost on Earth. Mars will be a bit more dusty but there is a much smaller search space to cover.

Both go to a prearranged meeting point (e.g. the north pole).

This seems too easy. Did I miss something?

thought the same thing, the devil would be in the details of the robot itself, the "how to get to same place" bit seems fairly straightforward

Nice answer!