September of last fellowship, approximately 9 months before starting if you are going down the list of posted advertisements. If you are networking, make your interest know as soon as possible.
Agree with then above. If you're networking or have a need/desire to stay in a particular area, let groups know well before. They may have particular needs that may affect which fellowships you apply for. Otherwise, the autumn before is about the right time.