Two other solutions (besides Live Search, Map24, mad4pda, and Virtual Earth):
Google Maps for Mobile for the Treo 700p (fancy Palm OS touchscreen & transparency version) courtesy of:
http://styletap.com/
->I wonder how the performance of this compares to the Java version described in this thread?
And, there's a virtual GPS solution available that should work for anyone that doesn't own real GPS hardware!
Use this for your mapping program:
http://www.mgmaps.com/
And this for simulating GPS!
http://www.mgmaps.com/news.php?item=67
http://www.navizon.com/FullFeatures.htm