From Wikipedia's Desire path article:
A desire path ... is an unplanned small trail created as a consequence of mechanical erosion caused by human or animal traffic. The path usually represents the shortest or the most easily navigated route between an origin and destination, and the width and severity of its surface erosion are often indicators of the traffic level it receives.
Basically, a desire path is a natural road.
Let's, for now, assume that PlanetSmith will have the equivalent of the following Minecraft blocks: grass, dirt, coarse dirt, and path. My suggestion is that as players/mobs step on these blocks there is a random chance these blocks will spontaneously change into the next block on the list. So grass will turn to dirt, dirt will turn to coarse dirt, and coarse dirt will turn to path. Thus, as players and mobs navigate the world, paths between important locations will naturally emerge without the player having to explicitly do anything. Walking speed could also be progressively increased along each subsequent block to encourage the use of these desire paths.
NOTE: Random chance is used instead of a fixed count of steps to avoid having to keep stateful information for a large number of blocks in the world. The random chance can be tuned up or down to give the desired expected number of steps before a block transitions. Naturally, the higher the chance the "faster" the transitions will occur, and the lower the chance the "slower" the transitions will occur.
For example, if you want to know what probability to use so that there's a 50% chance a block will transition after N steps you can use the equation: P=1-(1/2)^(1/N). So if you want a transition to occur approximately every 10 steps you get a P of ~6.7%, but if you want a transition to occur approximately every 50 steps you get a P of ~1.4%, etc.