GPS would definately NOT be the solution, the resolution wouldn't be good enough. A quick brainstorm (i'm sure there are much better ideas out there):
Remote control the mower through the path the first several times, recording sensor data as you go. Then play back the recording. Obviously this will not playback the same exact route each time due to many different variables but would give the robot a general path to follow. To improve on this use a variety of feedback loops to improve the results. Some examples would be sonar sensor readings, IR range finder readings, encoders, position beacons throughout the yard for navigation, multi axis gyros and accelerometers, magnetic compass, etc.
From a programming perspective, a neural network may be useful in a situation like this since they are great for pattern recognition. In addition, you can provide supervised learning by correcting the robots route with your remote control.
Also, I wouldn't expect this to be a cheap project.
