[This answer is a community wiki. Please contribute any other interesting and relevant articles or examples to list at the bottom.]
In a slightly different vein to answers so far: don't approach people first, just shoot them. This is mostly for practical reasons; you don't get good street photography by asking permission first (though you will get some great portraits that way).
Some examples in action:
Something you will see in common in these: they are all at ease. Even Meyerowitz bobbing up and down excited about the dogs - he's relaxed. They keep their cameras in their hands, raise it, frame and take the photo quickly, and lower the camera. Then they engage, briefly, and usually non-verbally. Even the quiet and contained Jeff Mermelstein gives a smile or a nod. This isn't impolite or aggressive, it's just a different set of mannerisms and timing.
In as few words as possible: Take the photo quickly and without fuss, then look at the subject, smile happily, and mean it.
That's where you engage your subject, and reassures them this is all totally normal and that you're not doing anything sneaky. It happens quickly, so it's not a big deal. This type of body language, communicating comfort and calmness, works incredibly well. It does not take as much practice as you might think, and you need not be the social butterfly extravert type; again, just look at Mermelstein!
In my several years of shooting street and trying to emulate this approach, the most usual reactions I've seen, in order:
- Nothing/vaguely puzzled (60%)
- Smile back
- Ask me about my camera
- Apologise for being "in the way"
- Annoyed enough to confront me in some way
When you are confronted (it happens), remain happy. Remember that you have a right to be doing what you're doing, and also remember that they have a right to be annoyed. Be respectful and listen. Do not argue or contradict, instead attempt to calm and disarm. If they're yelling at you, often the best thing to do is to walk away. How to deal with all the different possibilities is a whole article in itself, but the thing to remember here is that this is actually quite rare; I've had conversations like this maybe a half-dozen times in total, over about five years of actively shooting street photography.
Other articles and links (please note the date of addition so people can skip to the bits they may not have read yet):