Once upon a time, if you wanted navigation software you had to pay for it - through the nose. Rightly so, as the raw map data was so expensive. But times have changed and with Microsoft, Google and Yahoo all pushing out street data and aerial photography for free like there's no tomorrow, you won't be surprised to note that there's now an awful lot you can do for free. Here's a roundup of the smartphone-related solutions that are currently free, apart from data charges, but I'm assuming that you've got flat rate data or at least a sensible tariff from your provider.
Note the Java versions will also work on UIQ phones, although not all are optimised for this platfrom.