Seriously, I think anyone who wants to shoot street goes through this. Here's what I've found worked best for me.
1) Get a really small, quiet unobvious camera to start. I used to try to shoot street with my SLR and it just didn't happen for me. I bought an Olympus XA on ebay and dedicated myself to always having it with me and shooting and my street shooting took off. When I wanted more control I moved up to a Leica. It's not the camera, it's your attitude toward it but feeling stealth, made me stealth.
2) Shoot a lot of crappy pictures that demonstrate your fear. Eventually you get tired of shots of people backs, shots that are too far away, shots that are taken too late because you were too afraid to press the shutter at the right time etc. You either get disgusted with yourself and quit or you get disgusted with yourself and start taking better pictures.
3) Always have your camera in your hand and ready to shoot. When I step outside I guesstimate the light and set my camera's aperture and shutter speed and set the hyperfocal for about 8ft before I start walking. I don't use any kind of strap or anything. If a shot happens I can shoot from the hip or raise it to my eye and fire the shutter without thinking. 90% of the time, I'm pretty close. If the light changes I move the settings with the camera in my hand while I'm walking, usually without looking at it. (Leica's are nice that way).
4) When you are in the groove, shoot more. I spend a lot of time walking around with said camera ready to go and not shooting. Sometimes I'm not feeling it. Sometimes however everything comes together and the shots come like gifts. Sometimes I finish a roll and decide not to re-load and head home. And the shots keep coming and I curse myself. Don't do this. A corollary is always carry a few extra rolls.
5) Find a technique that works for you. I tend to shoot fast and I shoot while moving. Some people like to stand in one spot and wait for shots to happen around them. My biggest challenge is cutting my reaction time so that I'm taking a picture as I see it form.
I sometimes think of the scene in Butch Cassidy and the Sundance Kid where they first get to Bolivia and are trying to get jobs. The guy who is their potential employer wants to know if Sundance can shoot so he throws a can out and tells Sundance to shoot it. Sundance pulls the gun from his holster with a flourish and is about to shoot and the guy stops him, takes the gun and tells him to just stand there and shoot. He misses every shot. He then asks "Can I move?". He pulls the gun from the holster pivots around and blasts the can five times down the street. When the smoke clears he says deadpan "I shoot better when I move".