The Google Mobile Blog has made the happy announcement that voice search is now available in Hebrew and Arabic for users in Egypt, Jordan, Kuwait, Lebanon, Qatar, UAE, and Israel — support isn't limited to just those regions, but the program should be able to recognize the dialects spoken there. Google gathered over a million spoken phrases to initially "train" the system that will continue to learn the languages as people use it.

If you use Android 2.2 or later, just reboot your phone and the languages should show up in the Voice Search settings; otherwise, you'll need to download the updated app from the Market or App Store. We tried it out, but it doesn't seem to work that well with a thick American accent.