Google Maps help!

From homescreen, Menu -> Settings -> Applications -> Manage Applications -> Find Google Maps -> Clear Data and/or Clear Cache.

Google Maps also has a very helpful tutorial on clearing search/map history. Within Google Maps, Menu -> More -> Help -> Scroll to Search History or Clear Map Data and History.