I think you will need to be running Android 2.1 in order to be offered Google Nav in the Market or to use it. So if you are still on 1.5 you need to upgrade to 2.1. It is not a separate app in the Market, it comes as part of Google Maps, although you use a separate shortcut to it.
Google Nav is not too bad. Not as good as paid for apps for several reasons. It downloads the mapping information as you use it using wifi or, more likely if you are outdoors, mobile data. So you need a data inclusive phone package or deep pockets. At the moment you can't store the maps on your SD card as you do with a "proper" sat nav app.
It does include free live traffic which is not too bad. But it does not support any custom POIs. You can add a few favourites but not hundreds of petrol stations or hotels, etc. To make up for that it does have a very good search facility, which can be voice activated.