How far in advance should you estimate stories in your backlog?
My concern is that estimates that are 6 months out will become out of date as you develop features in the current sprint. I thought that with agile you re-estimate your current sprint.
Estimates do become out of date. We gather more information and learn new things, and some jobs will seem easier than they did a week ago and some will seem harder.
Why do you think that's a problem?
An estimate is nothing more than an educated guess, based on all the information available to you at any given time. It can be changed. If you find that jobs that involve file access always take longer than you estimated back in June, increase the estimate on all jobs that you know involve file access that you estimated back in June. Reestimate any other jobs that involve file access that you've estimated in between.
Or, when the business decides to add something to the upcoming sprint, if you look at it and think "We must have been mad when we estimated that!" then don't be afraid to tell the product owner that. It keeps their expectations under control.
The fact that estimates are going to change is never an excuse to not estimate them now. If you don't then you'll never spot that tiny job with medium business benefit among the massive jobs with massive business benefits.
It will change. That's okay.
Your backlog will most likely become out of date during and after every single sprint. This is why backlog grooming is important. Your PO should see to this along with help from the team.
If your backlog is manageable, it's good practice to re-estimate the entirety of it during pre-planning / planning meetings, to give a more updated overview. Along with a well estimated and established velocity, this should be enough to give the stakeholders a high-level overview of the project and it's future - as long as they accept the iterative nature of agile development.
Our practice was to estimate stories as they were created (if possible) and to add a flag to the fib number to indicate that it will need to be resized closer to implementation.
In our case, the flag was a .1. (ie 13.1 means that "we think this is a 13, but we should revisit that later.)
How far ahead you should estimate depends a lot on the needs of your business.
If the product owner wants to know when feature X could be expected, then you need an estimate of feature X and all features that come before it on the backlog.
If the product owner wants to know what he can probably release for the Christmas sales, you need to estimate the stories until you have enough to fill the sprints till then.
With that said, the estimates do not all need to be equally detailed and must not be cast in stone. The product backlog should contain approximately two sprints worth of stories that are fully detailed and where the team has a reasonable confidence in the estimations. Any stories that fall beyond that can do with less detail (more uncertainty) and estimates that are correspondingly less confident. As you go further in time, the stories are likely to become larger (more like epics) with according estimates. This isn't a problem, as those stories and their estimates will/should be revisited as they come nearer implementation and the knowledge about them grows.
The reason for having two sprints of fully estimated stories is to lessen the workload during the sprint planning (you don't have to estimate the stories as well) and to ensure that the team can pick up new work from the backlog if it turns out that they have time left at the end of the current sprint.
The reason for not casting estimates in stone is because they should only be used as an aid to the team to determine how much work they are committing to for a sprint. The only thing that should count at the end of the day is whether the team made good on their commitment.