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
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.