Really sorry for the long answer. It's the product of too much coffee.
tldr;
Kill off the people that weren't going to live long with, for example, a virus that shortens your telomeres.
--
When you think about evolution you have to think about one thing above all the others. Reproduction. Evolution is driven entirely by and for reproduction. If we're smarter than homo heildelbergensis then it's because being smart helped us reproduce. It either helped us find resources or stay away from danger, but the reason for being smart is so that you can indirectly, reproduce better. To turn it on its head, if being smarter only meant that we all became basement dwellers and never saw the light of day, we wouldn't be very sexy, and probably wouldn't reproduce. If that were the case the species would not become smarter.
Fitness is a term that in this context means reproductively fit. Your fitness is basically how well you reproduce. So if it's a thousand of years ago and you're big and strong and you're able to hunt and protect your family, then you reproduce. Your genes get passed on. Your offspring survive to become big strong people and so on. There are counter examples where being bigger might be a disadvantage but let's leave those for another discussion. This is just a simple example.
Another important thing to remember is that evolution does not go towards anything. There is no end goal in mind. A bear has a white coat when its brothers and sisters all have brown coats. The white coat helps him hide in the snow. There was no force that was driving him towards whiteness, it just happened randomly and it turned out to be a little better than brown. He hunted better, got fed and that let him reproduce more than everyone else.
Now let's start the experiment. We want immortal human beings. How do we get there? Currently, "all things being equal" (they're not, I know), everyone of breeding age is reproducing. That means that people who will live to be older than 100 and people who will kick it in their mid 60s are all reproducing. Right now there's no fitness related to longevity. Everyone can start breeding when they're done puberty regardless of how long they're going to live. So that would need to change.
Let's just say that since we do have a goal in mind (immortality), we can build to that goal gradually and have intermediate goals (longevity). So we allow for some circumstance that takes people who weren't going to live that long out of the gene pool. They are no longer reproducing. Not with our octogenarians, not with each other, nobody. Their short lived genes will die with them. Now we have a breeding population of very old people.
As other posters have mentioned, it really is about that reproductive age. Once you hit menopause you are no longer passing along your genes. Whatever you already passed along is what you passed along. If you live to be 300 after you hit menopause it won't matter because no one knew you were that sexy and you never reproduced more than the average person, let's say. So it's not enough to just live longer in and of itself, you must retain your ability to reproduce in order for that to be a fitness factor.
So that's it really. Those that won't live long must not reproduce (or reproduce as much, depending on how long you want the immortality process to take), and those that live longer must reproduce more. The question is how do you know? And that's what your original question is all about. What natural conditions will lead to this outcome?
Without knowing ahead of time who is going to die of natural causes early and who is going to age like wine, natural conditions can't really select those people. So you're going to need to invent a mechanism that can tell who is going to die early, either directly or indirectly. Here's where it gets interesting.
Imagine a virus like any other virus, except that it doesn't kill the host. It makes a copy, leaves a gene in your cell that says "do not infect me" and then leaves you alone. It's a whole other class of virus, real smart and sustainable virus. Let's add one curious effect of this virus: it decreases your telomere length (if you believe this is the basis of all aging and not a cumulative set of deteriorating genes or other mechanisms). So it makes everyone age. Everyone gets the disease, everyone is infected. Everyone is aging way faster than they should be. See where I'm going with this? :) So who lives? The people whose cells just happen to be slightly better at repairing telomeres. So they reproduce and only they reproduce, which leads to the start of generations of ubertelomeremensch.
This is one way but you could do it other ways. Maybe radiation from a star makes everyone age and mutate and only organisms with strong DNA repair (not just shielding) can survive. Basically, you want the people to die off who aren't going to live long anyway. That'll do it. You make the people who will live long more reproductively fit and they'll evolve to at least very long lives.
And we are talking about the species as a whole. If you wanted to do an offshoot and say "these jungle people over here bred mortality right out of their stock", you could do that too.
To be ever weary of the randomness of the process however, and as a counter example, evolution might prefer people with a certain protein or a certain overactive organelle. And, at first, it may have nothing to do with longevity, but through the course of random evolution it will provide the key function to repairing cells and DNA indefinitely.
Other interesting things to consider: the cells in your body come from your parents, those cells came from their parents, those cells came from their parents. If you follow the line all the way back you end up with some thing in our sweet mother Earth's history that found a way to reproduce itself over and over until we ended up with you. It might not be the same person, but it's life. That's called germ line immortality, and it's pretty dog gone amazing.
I had another point to make but I forgot it. Must be getting old.