I stumbled across the address autocomplete feature in one of my most recent CRM Online trials. When I set up the trial I was able to choose some of the newer add-ons like Field Service and Project Service.
I learned from other online blogs that the postal address autocomplete feature is added as part of the Field Service solution. Microsoft recommends that you get the trial here and then you can purchase it once you've tried it out.
The basic idea is that it tries to fill in the address once you've provided some part of it. For example, after you fill in the street address, it will try to autocomplete the rest of the address by providing potential options. Then you can select the one that's correct or ignore it and fill in the address yourself.