Disclaimer: I'm going to write from the perspective of statistics/machine learning research, because that's what I know.
If you want to apply for a fellowship, you should be planning it three years in advance of when you'd like to start it. This may see like a lot, but imagine you decide your CV needs a particular type of extra research project to round it out for your application. Starting from scratch, you might need a year to produce enough original research for a good paper in the area. Getting it published could easily take 6 months, from submission to the actual journal issue coming out (or the paper appearing online in its journal-accepted form). And fellowship application deadlines can easily be 9 months before the eventual start date. 12 months + 6 months + 9 months = 2 years 3 months. So give yourself three years, to be on the safe side.
This one is easy to screw up. So don't. Start writing your fellowship application three months before the deadline. Sure, that sounds like loads, but it isn't. Once you've planned and written the first draft, you'll need to allow time for proof-readers to get back to you, to incorporate their advice, to get the financial details sorted out, to get signatures from people like heads of department who are very busy and to give your core collaborators time to write reference letters for you (they're doing you a favour so the least you can do is give them a month's notice).
Also consider this: is there any reason not to start three months before the deadline? Really? If you get everything finished a fortnight ahead of time, you'll have had plenty of time to craft and polish your application. This isn't as important as the content, but an application that looks rushed and ill-considered does you no favours whatsoever.
Get advice from people
I guarantee there are people at your university that can give you useful advice about applying for a fellowship.
- Research Support Services
- People who have held fellowships
- People who have sat on grants panels
- People who are currently on the grants panel of interest
- Senior academics who have a lot of experience writing grants
And remember that even criticism is useful to you. If a senior academic is unimpressed with part of your application, ask yourself why. It doesn't matter whether you agree with them, the point is that if one person can be unimpressed then so can another. And that other might be on the panel. So be happy you've gotten some advanced warning and see what you can do to fix the problem.
Be so good they can't ignore you...
Steve Martin gave the above answer when he was asked for advice on how to succeed and it also applies in academia. For a fellowship it means take your professional development very seriously, learn new skills, work with very good people, make your papers as good as they can possibly be, give really good talks (by working hard on the content and learning how to deliver it well). "Be so good..." doesn't mean you need to be born brilliant; it means you have to do your best research and try to improve a little bit each and every day.
A large part in relation to your application is demonstrating your calibre as a researcher, which means writing top-rate papers, giving good conference talks and generally building up a strong CV. But remember that we care about all those things because they can be indicators of a good researcher; they're not important in of themselves. They should be a consequence of your becoming better and better researcher.
Collaborations and data sets
If you're applying for a fellowship to do statistics/machine learning research, you may well need some good data sets and collaborators. These can both be excellent drivers for your research programme, so put some effort into developing these areas. Statistics/machine learning is good for this because the researchers who produce interesting scientific data sets are often very happy to have someone offer to help with their data analysis, which then gives you access to good data on which to develop your new algorithms.
It's very easy to skip over this area, comfortable in the knowledge that it's the algorithms that are the important research outcomes of your work. But your proposal (and your research programme) will be a lot stronger if you put the effort into building some good collaborations and negotiating access to some genuinely interesting data sets.
Don't try to do too much
More good research is better, right? Well yes, but only if you manage to do it all. One of the common failings of fellowship applications written by junior academics is that they say they'll do vastly more than is feasible in the time allowed. Don't fall into this trap! The referees and grant panelists who read your application will be experienced enough to know you can't deliver all of it, and it just makes it look like you're no good at planning your research. Better instead to pick only your most interesting and important research ideas.
Specific details are key to making a good proposal. What are your research aims? Why is each one important? What classes of statistical model will you be working with (and why is that a good idea). What data sets do you have access to and what are their details (size etc). Not only do all of these help to sell your proposal, they also help clarify in your own mind what you're doing and why. If you can't write down in a couple of sentences why a research aim is important, maybe it isn't...
My fellowship plan always involved a contingency for being unsuccessful the first time around, simply because the majority of applications in any given round won't get funded. It's a fact of life that in modern academia there are more good researchers than there are fellowships to go round. So be persistent. Even if an application fails, it's helped you develop your ideas about your research programme and the feedback you've gotten along the way (and hopefully from the panel itself) means your next application will be even better. Not to mention the fact that your CV should have improved a bit in the interim.
Getting a fellowship is hard simply because there are a lot of good, smart researchers out there applying for them. But there are things you can work on that increase your chances and will these efforts tend to make you a better, more productive researcher as well. Win-win, really...