Has the look of Maps changed? If so, then you've got Maps 7, and on many devices Navigation disappears.
Navigation was not a separate app anyway, just a way of opening Maps in navigation mode. The functionality is still there in Maps, just you access it differently. Search on an address, select it, and you will have the option to navigate to it.
If you don't like the new way, uninstall updates using the Applications settings menu and you will have Maps 6 (and Navigation) back.