I applied for a Fulbright a few years ago, and I must say that if you'd like to apply for it for next year, get started now (or ideally several months ago). I didn't get the award, but I didn't start on my application until late, and I didn't have enough time to perfect my proposal. I would suggest getting in contact with someone at the university at which you'd like to study and find out what projects are going. This will help you get started on a proposal. I'm probably telling you things you already know, and if so, I'm sorry. I just remember what a stress it was when I started on my application so late.
As for other things you can do, I would definitely contact the department you are wanting to join. The department and the international rep at your university can help you loads if you let them. I'm not working on my PhD, but I was able to get a scholarship for half of my tuition thanks to my international rep's help (and a very well written essay haha).
If the department knows that you are serious and motivated, they will be willing to help you.
Amy