If you give the map app a lat/lon location to go to, it will work without a data connection. (
MyDirections works that way, and is a great addition to Maps.) But if you give it a street address, it has to contact the server to get the latitude and longitude of that address, so it needs an internet connection.