There are some institutions (Mayo) that charge for fellowship applications, but most are just the cost of the stamp and the paper. Bear in mind of course that the vast majority will require you to pay your own airfare and hotel (there are exceptions).
But there is no common application form, so every application is generally individual. So it's harder and more tedious. There is no real extra cost to you to apply to more programs (other than the stamps). But after about the 20th stamp affixing I would imagine you'd start to wonder what the hell you were doing.
Sometimes it is worth your while to email or call programs and ask them if they are accepting applications and if so, when the deadline is. That will save you time.
Fellowship applications suck. No getting around it. Some programs do it very well, efficiently, on an appropriate timeline, and keep you informed of progress. But there are far more who act like pseudo-black holes into which applications are tossed, never to be heard from again apart from an occasional escaping ray of light. Unfortunately, you never know the exact time nor the duration which these rays will be available. And each black hole is an entity unto itself.
Oftentimes, from what i hear, the only contact after submitting the application is a form letter or email 6-9 months later which says the position has already been filled.
