I just messed with a program called Nav Launcher for Android phone and it get to have working Google Maps Navigation on my HTC Magic. Note that I am currently in Bulgaria and official Navigation is not available here (Only in United States). After installing it i can only say it works like charm with navigating to contacts, or a typed/spoken destination. The only thing you need is installed the modified Maps with Navigation for use outside the USA.

In short you need to have 1.6 ROM on your Android and Speech Synthesis Data installed. You can do this either by going into the market and searching "SpeechSynthesis Data Installer", or on some ROM's, like CM 4.2.5, Menu -> Settings -> Speech synthesis -> Install voice data.
Next If you have root, download http://ul.to/uwa3gp/Maps3.2.1-patched-root.apk or http://files.legendofbong.co.uk/download.php?file=534750032-Maps3.2.1-patched-root.apk
Or i you do not have root, download http://ul.to/18fckr/Maps3.2.1-patched-no-root.apk or http://files.legendofbong.co.uk/download.php?file=1240234753-Maps3.2.1-patched-no-root.apk.
Now you have the patched Google Maps installed and Navigation should work for you.

After this you can install the Nav Launcher from here and get all the features like voice search working.

Here are some screenshots of Google Maps Navigation i just took.

Launches Google Maps Navigation in countries outside the United States.

Launches Google Maps Navigation in countries outside the United States.

Launches Google Maps Navigation in countries outside the United States.

Launches Google Maps Navigation in countries outside the United States.


See forum for more instructions.