The first thing you need is a goal.
And 5 miles a week should be your first one. I say that with the same all-knowing aire that Chef had in episode 5.07 when he proclaims that the proper age to start having sex is 17. Whatever you expect to get out of this, no matter how much or how little you want to achieve, 5 miles a week is your first step. If you are physically capable of running, then you are physically capable of running 5 miles a week. You just don't know it yet. Of course if you already run 5 miles a week, then congratulations, you hit your first goal (freeking over-achiever).
In 1994, when I was gearing up for my first marathon, my running coach/platoon leader gave me a piece of sage advice that has stuck with me for a long time.
"If you can run a mile", he said "then you can run 3". The rest I discovered on my own. If you can run 3, then you can run 6. Run 6 and you can run 12. Run 12 and you can run 24. And of course, if you can run 24, 26 is really not a big deal (I realize that 1 to 3 is non-linear with respect to the rest of the algo, but bear with me). It speaks, I think, to how close we all are to our goals in general all the time. Running as a sport scales very well, and all you have to do to prove to yourself that it's possible to run a long distance, is to run halve that distance. If you can run halve, then you are physically capable of running the whole, your mind just needs to catch up with your body. When I was in the USMC we did proofs of this all the time. If we knew we could run 7, and wanted to run 14, then we ran 7 out, and necessarily had to run 7 more to get back. That might not be a good strategy for you, there are variables beyond that to consider, (age for example) but the point is that it's possible.
I find that weekly based distance goals are good because the time scale allows for "real life" to happen. You can miss a day, or two, and still hit your goal if you have a week to get there. If you hit 5, 15 is a good next step. Once you're at 5 though, you kind of need to decide what you're in this for. If it's fun, then your goals are probably going to be more 'location' based rather than distance based. Maybe you want weight loss, or "cardio" in which case you'll have caloric or heart rate based goals. If you're doing the marathon thing, then you're probably going to want to start a 16 week training program. Most of the 16 week programs assume you've been doing 15miles a week sustained for at least a month, so 15/week is your next goal. In my experience, you don't really have to worry about the "sustained month" part. If you're at 15 miles a week, then you're ready to start a marathon training program.
Let's concentrate on getting you to 5 for now though. 0-5 is an important time, because it's when you're most likely to decide to go do something else. So there are some tricks to help you get that first 5/week.
:: Run with a partner
If you can get a training buddy, your probability of success is far better then it would be otherwise. As buddys go, there are some attributes that will help you out a lot in the long run. Always try to get a buddy that's better than you are. It won't do anything for them, but it'll help you with your pace, and if you can get a good pace just starting out, things will come easier. Also, if your training buddy is a bit competitive, it helps out a lot. Not aggro mind you, but a little "race you to that tree" never hurt anybody. If your training buddy is of the opposite sex, all the better, I find the sexual tension aids competitiveness, also for whatever reason you're less inclined to slack off in the presence of a (girl|boy).
:: Dont sweat the small stuff
You'll hear me talking about "a good pace", but you don't hear me talking about "you need to be running 6 minute miles". The reason for that is that things like pace and distance will come, as long as you're working toward something. Don't worry too much about weather it took you a minute and a halve longer to get your mile today, the important goal is 5/week for now. If you're having trouble with the rigidity of 5miles/week, run 170 minutes per week instead (hint: for most people just starting out it'll be about the same thing). If 5/week isn't challenging, then move on NOW and don't look back.
:: Run outside
I used to think that treadmills were superior because you had finite control over pace and distance. I've since come to the conclusion that running on a treadmill is a subtly altogether different kind of exercise. I'm not sure that I can articulate exactly why I feel that way besides A) I have more fun when I run outside, and B) running outside kicks my ass after I've run inside for a week or so. You may be different (you probably are), but I just don't get into the same mental state, and for that reason feel that it's easier to get started running outside.
:: Run "through it"
The first week or two, you may have at least one of three common pains, especially if you're a bit heavy. Shin-splints, lower back aches, or knee aches. Try to just run through it, I promise they'll get better after the second or third week. Running is something that sneaks up on you. For the first week or so, try freezing little paper cups of water in your freezer, and applying these to the pain spots for around 20min at a time. Avoid the liquid heat stuff, bad mojo that. For shin splints, I've found stretching for 5 minutes or so in the seiza position before and after a run is very helpful.
:: Put band-aids on your nipples
nuff said.
:: Get you some gadgets
If you're a geek, you'll go to great lengths to play with some nifty gadgetry. Enduring a few miles is nothing if you get to play with a running computer (you'll probably even run up mountains if it has an altimeter in it). Some people like music (personally I prefer to just sort of vege but to each his own), so an ipod or whatever might take your mind off things, and set your pace for you. I have a few gadgets I run with, and a treadmill (nothing impressive). It's fun for me to quantify the various statistics, and hey, gadgets are cool in general. Once I even got lost exploring a new neighborhood and used my Garmin Forerunner to navigate my way out. I'm sure I would have made it out eventually heh.