Applying for NSF (Math Fellowship) before being accepted to a university. How to find a Sponsor? I am in the process of applying to graduate schools this Fall 2017 (both in the US and in Europe). I do not yet know what institution I may go to nor do I know any researcher who would be willing to make such early plans. I am wondering whether or not my case matches the requirements of the NSF (Math Fellowship)? I have read the FAQs but found nothing that answers my concern. 

From the description for Sponsoring Scientist, I read 

The sponsoring scientist's statement is meant to
show how the host and host institution will provide a vibrant and
supportive environment for the Fellow's proposed research and
training activities and provide a basis for the Fellow's future
independent research career.


The above makes me think that this Fellowship is only appropriate for enrolled students. Is this right? 

If not and it is indeed possible/appropriate for me to apply for NSF (Math Fellowship), then how should I go about finding a Sponsoring Scientist? Is it appropriate to approach/email some researchers in some schools that I will be applying to?
You're looking at the NSF Mathematical Sciences Postdoctoral Research Fellowships, which is for funding postdocs, not graduate study.

You probably want the NSF Graduate Research Fellowship, which is the main NSF fellowship program for PhD studies in math and science.  This program doesn't have a "sponsoring scientist" requirement.