The builtin navigation requires a data connection when planning your route, either mobile data or wifi, the maps are stored on google's servers, and the route is calculated by google's servers. You *dont* need a data connection during the journey though, just when planning. I dont think the amount of data used during planning is that much to be honest, google maps are now pretty efficient with that.
Alternatively you'll have to buy one, e.g. Copilot live. This costs money but all of the maps are stored on your SD card and the route is planned by your phone - so no data connection is necessary (except one HUUUUGE download at the beginning to download the app and the maps).
Sony Ericsson Xperia Arc : GiffGaff : UK