Search is your friend; there are several threads about this topic. The recent Google Map update removed the Navigation app since that function is now incorporated in the Map app.
When you updated the Google Maps it Dropped the Nav Widget and also in this new update Latitude is gone as well or will be soon..
The Google map Nav has disappeared when I needed it most. Way to go Google. I would have paid for it if that was the problem ... instead left me lost. Other Navy apps suck and suck up tons of data to download. Thanks.
The icon is the only thing that disappeared. You have to go thru the Maps app, type in the address, then click the nav icon that you know and love so much and boom! Navigation.