It’s an essential skill, and the best way to develop it is by plunging in and writing proposals. The sooner you start, the better. Almost all proposals will have a few basic elements in common:

1. Narrative or Project Description/Statement of Work: This is where you describe, in as much detail as possible in accordance with the guidelines, what your research will entail, how and where you plan to accomplish it, why it’s important, why you’re qualified to do it, and what contribution it will make to your field. For any narrative, write to the sponsor’s guidelines and review criteria. For example, if the NEH lists six areas they look for in a narrative, write yours with a section devoted to each.
2. Budget: Often a neglected aspect of proposal writing, but utterly essential and possibly the most important. At this stage, you won’t have to worry about the myriad regulations when it comes to what’s allowable in a budget and what’s not. For your applications, you will likely be asking for travel money, stipends, or research funds. The best thing you can do is to be as specific and realistic as possible in estimating all costs: if you need travel money, research airfares online and come up with a reasonable average fare. For photocopies, estimate the actual number of copies. If you use real costs and are conscientious about being specific in your needs, your budgets will be fine.
3. Curriculum Vitae: It’s essential to have an updated CV. Keep it current all the time — that way you won’t forget to include something (no publishing credit is too small!) or be rushed when it comes time to submit an application.
4. Reference Letters: Most fellowship applications request them. Know who you would ask for them. Also know the deadlines, particularly if you’re applying for more than one fellowship. If the same references are writing more than one letter, let them know all the deadlines so they aren’t taken by surprise. Obviously, you should also give your reference plenty of time to compose the letter.

This is extremely rudimentary overview of preparing an application, but it will help get you started. For an excellent, more in-depth look at effective proposal writing, I recommend the Foundation Center’s “short course” on the subject. It’s available on their web site.