If you use the Google Maps service in any way, they request that you retain their branding. It is infact in the Terms of Service I believe, so techincally no it is not legal.
9.4 Attribution Content provided to you through the Service may contain the trade names, trademarks, service marks, logos, domain names, and other distinctive brand features of Google, its partners, or other third party rights holders of content indexed by Google. You may not delete or in any manner alter these trade names, trademarks, service marks, logos, domain names, and other distinctive brand features.
Reference: http://code.google.com/apis/maps/terms.html
While it is against the Terms of Service, this is however possible using CSS rules - however the below reference is using a GreaseMonkey script. It may be possible with an included Stylesheet.
Reference: http://userstyles.org/styles/1929