Well, GPS will work, but many of the GPS apps installed on your phone need a data connection to work, so you'll need to find an app that uses local maps. There are several in the Android market.
A list of GPS apps with local maps can be found here:
http://androidandme.com/2010/04/appl...n-for-android/
Google maps will NOT work, as they need a data connection to pull in their maps.