I'm assuming you are referring to the math postdoc.
Unlike regular career grants, the postdoc grant is tied to a specific location (usually, the mentor's home university).
I guess that working with someone else inside this institute should be OK (I think that formally the mentor will need to approve your reports to the NSF), but switching institutions is a big thing, and this will require an approval of the NSF (which have been granted in the past in several cases, at least that I know of, but you should not consider this is a regular thing).
You should really think about your application (in the sense of who is the mentor and where to apply), as your number one pick for post doc (well, I guess if you will get a Veblen instructorship, you would probably pass on the grant, but otherwise...).
There are several reasons for that:
First, If you get the NSF, in most cases, the host institution will usually offer you the prestigious instructorship position to complement it (it goes by various names depending on the institute, Veblen (Princeton), Dickson (UChicago), CLE Moore (MIT), Szago (Stanford), etc), as the NSF itself does not finance the whole 3 years. Moreover, you get the answers for the NSF application right before the first round, so you can negotiate with other institutions if needed to.
Second, If you get the NSF and choose to pass, in most cases, the NSF won't offer the grant to the next candidate (it has to do with their guidelines and also the coordinates offers rounds in math), so basically, this money is wasted.
Regarding the timing, now it is definitely the time to work on NSF applications.
Remember that the schoolyear is about to start in most places, so people are busy, and unlike regular postdoc applications (where your future mentor just need to email the hiring committee), here your future mentor will need to write down a letter to the NSF (so he would actually need to read your full application at-least a week before the deadline).
So you should work on both sides - finish your application (this not a wasting of time, as many of the materials will be used to your regular postdoc applications on mathjobs), and contact future mentors to see if they are willing to sponsor your NSF application.
Regarding who to contact, which order, and how to approach, this depends on the personality of the future mentor, and I think such considerations are better discussed with your adviser in person.