Usually, the big fellowships (e.g. NSF GRFP) for grad schools starting in Fall of year X are awarded/announced in Spring of year X. So, most admission decisions are already made prior to the fellowship decision. Although you are generally eligible to apply for these fellowships in your senior year of undergrad, you are not able to defer them other than very specific reasons (e.g. medical, military etc.)
Also, these fellowships are tough to win as an undergrad as you are competing with 1st and 2nd year graduate students. Except for a few special cases, I would say that if you are able to win something like the NSF GRFP, you should be able to gain acceptance to graduate school. I could think of a few exceptions where the student did not apply to a large number of schools or applied to really bad fits and could end up with a GRFP but no graduate school, but I think these are quite rare.
There are smaller fellowships than things like the NSF GRFP but since they are smaller and worth less money, I don't think they would make much of a difference in an admission decision.
So, overall, I don't think fellowships will make a huge difference in your results. I don't think a plan where you apply to graduate schools with a fellowship already secured is feasible, for the reasons above. What I would suggest is to apply for the fellowships in the same year as you apply for graduate school. The results may come out just before the April 15 deadline, and that might be enough to convince a school that originally put you on the top of a waitlist to offer you a spot, or for you to move up several spots on a waitlist. Maybe! But in any case, you should not feel discouraged if you don't win an external fellowship prior to grad school as you can still compete for them as a new graduate student!