Edit: Solution

Brut.all got it working.  Here are some more in-depth instructions for those of you having issues:

First, uninstall the current Maps app.

adb remount
adb shell rm /system/sd/app/*Maps*
adb shell rm /system/sd/app/*maps*
adb shell rm /system/sd/dalvik-cache/*Maps*
adb shell rm /system/sd/dalvik-cache/*maps*
adb shell rm /data/app/*Maps*
adb shell rm /data/app/*maps*
adb shell rm /data/dalvik-cache/*Maps*
adb shell rm /data/dalvik-cache/*maps*
adb shell rm /system/app/*Maps*
adb shell rm /system/app/*maps*
adb uninstall com.google.android.apps.maps

Then, update your build.prop file. This could be build.prop, build.trout.prop, or build.sapphire.prop. On CM 4.2.5 running on the HTC Dream, it's build.trout.prop.

adb remount
adb pull /system/build.trout.prop .

The ro.build.fingerprint line needs to begin with verizon/voles/sholes/.  Nothing else in the file needs to be changed.

adb push build.trout.prop /system/
adb reboot

Then you need to install the SpeechSynthesis Data. 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, install the modified Maps app from Maps.apk.

adb install -r Maps.apk

Now open up Maps and search for directions between two US addresses, such as "Buffalo, NY" to "Syracuse, NY". You should be given two options: "Show on map" and "Navigate". If you don't have the "Navigate" option at this point, please read [Think Tank] Modifying G1 to enable Navigation - THUNK! - xda-developers.  You won't be able to get Navigation to work outside the USA until you have it working inside the USA.

Unfortunately, you can't search for a destination outside of the USA in Maps and navigate to it. It will not give you the option. However, you can create a shortcut on the home screen to an address, and it will work. From the home screen: Menu -> Add -> Shortcuts -> Directions. Enter the destination address, choose the car under "Travel by", and check "Turn-by-turn navigation". When you tap this icon, Navigation should launch with your intended destination.

Reply to the thread if you have any issues.

I guess the next step is trying to get Maps to show the Navigate option for any destination, but what has already been accomplished is amazing.