Always such good questions! Well, let's see. There are several ways to go about it, but most of them involve jumping right in. When someone comes to a psychologist for a phobia, let's say, most psychologists will start with a form of cognitive behavioral work called "exposure therapy." It's really the only empirically validated way of getting over a major phobia or fear.
So, for example, let's say someone comes in with a fear of speaking in public. We usually spend some time talking about how they think the fear developed and what specifically they're most afraid of (i.e. "what's the worst that could happen?"). In that situation, the typical answer is that the crowd could ridicule them or they could possibly hyperventilate (in very bad cases). However, neither of these "worst possible" outcomes involve death (the ultimate worst case scenario). Then, we might spend some time mulling over how likely it is that this will happen (i.e. how likely is it that a crowd will actually heckle you?). When someone fears something, much of that fear is irrational. Thus, while the person may be afraid of the crowd jeering them, the actual likelihood that it will happen is pretty low.
Finally, after we've talked about all of it, the exposure part begins. It starts with small doses of whatever is feared and a rating of how bad the anxiety got. So, for talking to a pretty woman, I would require the client to start a conversation with a girl that they find mildly attractive (think a 5, not a 10) and have the conversation be short. After it, I would ask them to rate their anxiety. How bad was it? Did the worst possible thing actually happen? If it did, would it kill you? Etc.
Eventually, the client would be required to work their way up to talking to a very pretty girl. However, this would come after repeated exposures to less threatening scenarios. The result is that the anxiety will decrease over time so that the feared situation becomes less scary.
Personal note: When I was younger, I had a roommate who was terrified of asking women out - and he had a good reason! He had been literally stood up at the alter the year before. So, we made a game out of it. When we went out to go to work or whatever, both of us would bet the other that we could rack up more rejections in a day than the other one. We'd come home and shout, "how many did you get today?" (my alltime high was 8) We would both just indiscriminately start conversations with people we found attractive and try to get rejected. That was the goal, essentially. Whoever won had to buy coffee for the other.
During this whole thing I went on some very interesting dates with guys that I thought were totally "out of my league" because I had assumed they would say no, but they didn't. And in the end, my roommate met who was to become his future wife. They've been married for 6+ years now and she is pregnant with their first child. He still jokes that she's out of his league (she's VERY pretty), but they're very happy!
Good idea. If you make a game out of it, it's actually pretty easy after a while. You have no expectations, so when something comes of it, its a pleasant surprise!
PS - I have a feeling that if you get some good results, your friends might be willing to play along after all...