I have traveled around the US plenty with my own children, occasionally but not often with other people's children, and I don't recall anyone ever asking me to show any proof that my children really were my children. There is no law requiring you to have any sort of document to be allowed to take the child on a trip.
I don't see much value to having a notarized letter from the parents. If something led the police to think you kidnapped this child, I'd hope they wouldn't drop the matter because you showed them a notarized letter. A kidnapper could easily forge such a letter.
The only real value to having a notarized letter from the parents would be if they later changed their minds and said they never gave you permission, or if the whole thing was a trick so they could charge you with kidnapping. Then you would have evidence that they really did give permission. Frankly, if I thought there was the remotest possibility of a chance of something like that happening, I wouldn't even be speaking to this child without a lawyer present, never mind taking him on a long trip.
If the parents are separated or divorced, I'd make sure that both parents agree to let you take their child on this trip. Otherwise you could get in the middle of a custody dispute. I definitely would not want to find out that I was the dupe for one parent trying to hustle the child out of state to hide him from the courts in the middle of some custody battle.
It is a good idea to have a letter from the child's parents giving you authority to get the child medical care, and giving the name and phone number of their insurance company and their ID number with the insurance company. Just in case the child is injured. Again, I've never taken someone else's children to the emergency room, but when I've taken my own kids, no one has ever asked me for any proof that they were mine. I'm guessing that there probably isn't a big problem with people picking up random children and taking them to the doctor.
If you take someone else's child to a different COUNTRY, this is a whole different issue.