I worked on this very problem...
For a LEGO robot I built. I never finished it, but it was due to time, and not a technical problem. I managed to get it to report its location fairly accurately, even!
First, it needs to map the yard - where everything is. Use proximity sensors on the two front corners to judge how close it comes to any given object. It drives around the outside, then fills in the middle.
Once it's mapped everything, you can download the map, and mark said map to tell it where it's allowed, and what boundaries exist that it missed (say, a gate), or that don't exist that it thought it saw (someone stood in front of it). With the right software, it can tell where it is by guessing its general location based on distance traveled, then match that location to a nearby landmark. Or, as long as it knows the outside boundary, just have it follow its own cut trail...
I would suggest an exterior brain, though; a computer that talks to it over WiFi, controlling its actions. That would give you a way to visualize its progress - and make it much smarter - without adding a lot of weight. That, and you can make it run on Perl scripts.