Reclaiming the moral high ground [tm] :-) ...
For comments on "street" or people-photography generally see my answer here.
For answers on reclaiming the moral high ground from the creeps and perverts, read on ...
It's interesting to note that while I probably address the or a major aspect of David's question, and others tend not to so, or do so only obliquely, I've had neither votes (up or down) or comments. The few "creep" comments are in separate answers or comments.
But I'm not overly surprised and it's not surprising. This is an immensely emotive subject, and many or even most tend to 'go with the flow' and accept the societal excesses and attached implications. Which is understandable, but a shame. Fleeing into metaphorical 'gated communities' in response to the creeps, perverts, pdfls and their ilk is similar to the affect that terrorists have obtained in the western world with relatively modest effort. I was (of course) well aware that I was 'sticking my head up' when I 'penned' this answer.
While offence of parents or educators or whoever is not an aim, I consider (voice crying in the wilderness) that photographers might wish to consider reclaiming the moral high ground and not letting the perverts ruin everyone's lives. Doing this while not annoying or disturbing people is the challenge. I usually manage OK. Usually :-).
Legality varies by country and, as you are in the US, Michael Clark's answer looks very good. But, do your own research.
I take many photos of an extremely wide variety of subjects - many of people and many of inanimate objects, scenes etc. I'm careful with photos of children due to societal concerns. All such of my photos are legally taken and I seldom run up against parental concern but it does happen.
I'm either very open or "carefully covert" with my photo taking and in the latter case maintain a very active awareness of how others would judge the photos if reviewed. If it suits I'll ask parental permission. If I've taken photos of children without asking parental permission I'll seek out the parents if the situations suits. Here in New Zealand, on one only occasion in recent memory have I been asked to delete photos of a child. That was after I sought out the parent and the photos were wholly innocent by any measure. (I'm legally permitted to take such photos under NZ law but deleted them without complaint. I know that I'm "harmless" - the parent can not be sure.)
I have been accosted loudly on one occasion by a 'grandmother' - in Singapore. I had not taken a photo at that stage. (Shame - lovely (potential) photo of 2 children on a large rug in a shop display.)
I'm occasionally surprised here to find children who advise that parents/aunt or whoever is not there or far off. Nice that the country is in fact very largely trustable but still somewhat concerning. I find that requests to delete photos or expressions of anger or concern are extremely rare. I have had a few other delete requests re adults and in one case re piles of freight pallets. I may comply but in those cases I may well first explain that I'm legally allowed to take the photos and why what I am doing is "reasonable enough". Where children are involved a quietr approach is in order for the parent's sake.
I had one lady approach me at a beach after I'd been taking occasional photos of birds (flying type) and scenery for perhaps half an hour while picnicing with my wife. She demanded that I delete any photos of her and demanded to see my photos. I did not know if she'd happened to get included in any of the photos and was amused, on reviewing them, to find that she wasn't in any She stalked off, wholly unapologetic.
The need to take this sort of care is a shame but there are too many sick people in the world for a photographer to be blissfully unaware of the potential implications of ones actions - even when legal. But equally, the need to not be cowed by PC rubbish is, for me, a strong imperative - as you may have noticed if you've read this far :-)
By contrast:
I have taken a large number of photos in Asia in recent years. Mostly China but also Malaysia, Singapore, Brunei, Macau, ... . I find that in Asia and especially in China reaction to one's taking photos of children is almost invariably positive. Whether asking in advance or showing people afterwards almost invariably produces an enthusiastically positive response.
In China younger women seem more likely than older women to give permission, old men are perhaps less likely than old women and young men are usually happy (but more often bemused :-)).
"Last train to Shuanalong" - no arty quality photos here folks :-). Facebook resolution and quality - somewhere between street photography*, trip record and train-of-consciousness street wandering through (mostly) outer city Shenzhen. Many high ISO hand held walking. Some candid "unseen" (sometimes), some with permission. [[* "Genuine" [tm] street photography seems to have to be in monochrome. In fact, the transformation in effect is quite stunning - even if just converting colour images which have not been taken with a monochrome mindset. For trip record / long term memory embedding I find colour better.]].
Move to Asia :-)

Higher resolution version here - 7900x 2700
FWIW - and how much is moot, all the above except perhaps the upper middle one would have had parental or responsible-adult permission given before or afterwards. All these were taken in China. As noted in the text, in my reasonably extensive experience, openly taking photographs of children in public in China is almost always welcomed.
**(In China almost every individual child is THE family of the parents concerned - very special). ** I imagine that they are proud to have someone else take an interest in their family.
In any situation whether asking in advance or after taking a photo I'd share the results with the responsible adult as of right where possible - as much because they and I would both enjoy the sharing as for any other reason. email addresses often obtained. (Children are a small but non trivial portion of the subjects of photos that I take in China).
Added - mid 2014:
This is of direct relevance to the question.
@Jasmine - Thanks for the comments. Since writing the above I've been in India for 3 weeks, taken many many photos with a very wide range of subjects - and found that they too are much more relaxed about strangers taking photos - not only of children but largely 'across the board'. It's not uncommon to walk along a street with SLR at hip and be greeted by calls of "photo, photo" from bystanders.
And I've had two quite traumatic experiences, one where I took a series of shots (about 10 in quick sequence) of a Magpie flying, found on inspection that two frames just before the end had the bird flying at low level just behind a young girl on a scooter, some distance away. View of girl on scooter was from side rear. Two frames with her and bird were cute enough that I found the parent who was interested. We exchanged email addresses. Saw he was with NZ police. No problem, of course. Or so I thought. Story gets complicated but he subsequently filed a complaint as a member of the public to provide grounds for a police officer to visit me on an unrelated matter where it was claimed a complaint had been laid at another unrelated location. They were looking for "suspects" and used the complaint to enable a plausible 'fishing expedition'. The latter location was a skateboard park which I drive past occasionally and had often wanted to visit when I had time, but had never managed till about 2 weeks after the Magpie photos. At the skateboard park I took 200+ photos - many were of a talented young man (late teens) with a bicycle on a "half pipe". He did several 360 degree backflips (!!!) and a large number of aerial 180 degree jumps - some over my head as I stood on the rim of the 'pipe'. Magic. The visiting police officer lied about why she had visited and the original off duty officer also lied in important ways. As I was unaware of the lies until afterwards I was happily cooperative and provided ALL the photo sequence from the skateboard park plus ones either end of the sequence. She was thus satisfied as to my purposes. [ALL photos taken were completely allowed by NZ law and I was also not obliged to show the officer the photo sequence, but I did]. I subsequently found that the original lies are still on my police record and available to any organisation who asks for a "vetting report". It has the potential to affect any prospective photography work for organisations who decide to ask for a vetting report - as those involved with children are advised to do. This is not how our police system is intended to work. Work in progress :-).
One day at Te Pai - 271 photos