"Preamble" - "Candid" versus "permission granted" photos:
You specifically ask about asking permission, so that's what I've mainly concentrated on below. As others note and as you will be aware, photos taken when the subject is aware of the photographer are usually quite different from casual / candid / spontaneous shots. I take both. If I see someone who I would like to take a 'posed' photo of I may take several candid shots first and then ask permission. Afterwards I will often show them the whole set. Very occasionally this gets an adverse reaction, but not usually.
Sometimes I may ask permission to take photos generally and then "fade into the shadows" and take photos over a period, getting back towards the 'fully unawares' mode.
On other occasions I "just wander" taking photos as situations present. These will range from "fully unaware" through "camera obvious and maybe acknowledged but no verbal interaction" through fully permission / posed shots. The photos below and in the referenced album cover a wide range of situations.
This works for me. What works for you will vary:
Look like a photographer. ie make it obvious that you are taking photos.
Catch their eye and smile at person as you approach them. They will usually smile back. Doing this is a good ice breaker. It doesn't guarantee a result and a lack of smile may not mean a failure, but it is usually a good start.
As I walk towards a person I will often raise the camera in my right hand so the lens is upwards and pointing skywards, look at them, wave the camera a few times and then bring camera down while looking at them with a query gesture. That's far far harder to explain than to do :-). ie I am showing that the camera is not pointing at them but that I am taking photos and would like to take a photo of them. I take a reasonably large number of photos like this where the subject and I share no language at all and the gesture needs to be obvious enough but non threatening enough to not need any spoken language.
If people ask why you want to take their photo, know what you are going to say. It doesn't have to be for a newspaper or anything formal, but know what you are going to say - many will still say yes. The majority of people that I approach this way will agree to have their photo taken.
Have some handout slips available that give your contact details. If you are going to put the photos on a website show the web address. I write the photo ID on the slip (camera frame number) and tell them to quote it if they email me.
Doing this at shows etc is easier and gets an even better than average accept rate.
If there are two people together they are more likely to be happy to have their photo taken together if they are otherwise uncertain. In such cases I may take several photos and frame them together and individually and then show them the results. I may ask if they would like me to delete the individual shots. Very few do.
People, women especially, tend not to like their own picture, even when they look nice. I point out that most people like photos of others but not of themselves and that those who are shy should ask a friend whose judgment they trust what they think. I often enough have the subject saying 'delete" and the friend saying 'it's lovely". Lovely usually wins.
If it seems useful offer to take a photos or several and then delete it/them if they don't like the result. You'll usually get some keepers from a small batch.
[This album of photos][http://J.MP/RANDOMSTRANGERS] is offered not for any photographic merit per se, but as examples of photos of total strangers. Some are obviously taken "unawares", but the large majority obviously are taken with the subjects approval. Most are somewhat posed - which is what tends to happen when you ask, but some are less so. If I'm going to ask I may (not always) take a number of shots first to get natural poses and actions and then ask and in any case show them what I have taken. In a very very very few cases I get adverse reaction. Very rare.
If children are involved I will usually either ask in advance or seek out the parents afterwards and show them the photos and ask if they are happy for me to have them and whether they would like me to send them to them. Again, adverse reaction is extremely rare.
Women are easier to approach than men. Women expect men to want to take their photos:-) - Men may wonder why, or be less comfortable.
Unposed - Posed:
Prague - she was posing, but not for me.
Unaware of photographer - quite different than when the subject expects to be photographed.
Shanghai - uptown (far from "The Bund", not fancy, far more fun.)
Unaware of the photographer but I am not "hiding".
Aware of the photographer:
Tian an men square
The classic street lens is probably a 50mm prime on a full frame and 35mm prime on an APSC.
My walk-about lens is an 18-250 (!) on an APSC but for street scenes I find the 18mm setting is most useful. (= 18mm on an APSC = equivalent of 27mm on a Full Frame 35mm camera).
Distortion happens if not careful.
You are almost in someones face if they are filling the frame. If you are other than right on top of them you get a fair amount of background.
Being able to zoom to 250mm in an instant is vastly useful when sudden opportunities present.
I also use a 50 mm f/1.8 prime and a lovely 17-35mm f/2.8-5.6 (almost a zoomed prime :-) ) BUT they are far more restrictive and harder to get a good result. Street photography usually does not need every possible bit of optical quality - its more about getting a picture you are happy with. So a lens with a flexible zoom range may be seen as cheating by some, but means you are always ready.