How do I use voice input in Google Maps on a HTC Desire?
I have a Samsung Galaxy S on T-Mobile, so YMMV.

To use voice entry, I start the Navigation application, not Maps; one of the menu options it displays is "Speak destination".  Navigation wasn't available on the phone when I first got it; I first noticed it about a week ago (I noticed Latitude and Places arrived at the same time, so might all have been part of the same push).

EDIT: To get voice entry in Maps, press and hold the Search key, which gives you a general search.  To search for a location, I use Menu > Search, then there's a microphone icon on the search bar.  In Menu > Directions, you can focus on either the From or To input boxes, and again you'll get the search bar with a microphone icon.  If I use Menu > Directions to speak a location, it works as if I'm doing a map search, so I have to go back and select the location again in the Directions input box.