You can do it right out of the box with Google Talk, assuming the person on the other end has it. I video chatted with a friend using Google Talk, with him on his computer and webcam. Video chat via Google talk is not an option for him yet on his EVO 3D. I also installed the Tango video chat app and did video chat on his phone. I was on 3G, so it was pretty bad, but it worked. Skype is also an option but we didn't try it.
@tennisfan I just bring up the Google Talk app and it logs me in and gives me a list of contacts. If the contacts have a little camcorder icon next to them, and the icon is green, then they are logged in and you can video chat to them.