Sensor systems for this type of application already exist:
http://www.xbow.com/Industry_solutions/Land.htm
I have a Garmin eTrex Vista handheld gps which includes a data cable to interface with a PC. The output follows a standard format but is only updated maybe once per second. There is an article on the Parallax web site that has sample code to use a Stamp as a data logger for a model airplane. I have no idea whether WAAS is active out there, without it you'll need a DGPS receiver.
There is another Garmin product called MapSource that has very detailed topo maps of the whole United States. I don't think they include metadata though, I'm pretty sure they're just maps. You'll need to find or build a detailed metabase to go with the maps.
Based on the presentation I saw on the contest website, there are some rough roads and trails. You might want to consider using them to your advantage. If you analyze the terrain you will probably find corridors that are easier to navigate than others. Your low-level behavior will be to avoid dynamic obstacles, but your high-level behavior will follow a map. You'll need a pretty solid application to take a set of raw waypoints and find the optimal solution between them.