Everyone starts out with no publications. Never mind starting a PhD in that condition: I finished my PhD at a top-three program for my field without any publications, and I still got a good postdoctoral position. How did I do this? Because of my advisor's recommendation. (And it was a sound recommendation: eventually I did get some publications...)
For graduate students -- and especially, early career graduate students -- recommendation letters are all-important. Do you have a thesis advisor yet? If so, go directly to her and tell her what fellowships you are thinking of applying for and asking whether that sounds reasonable and whether your application will be competitive. If you do not have a thesis advisor, try out the same conversation with several faculty members in your department that know you through your coursework, research or TAing. Emphasize that because you are young and unpublished, you think you will need strong recommendations from them to get serious consideration for summer research fellowships. Select from among these the ones who sound most enthusiastic.
In general, faculty in your department should be very supportive of your endeavor. On the one hand, such fellowships generally provide funding, and faculty are always very happy when graduate students can find external funding of any kind whatsoever, since internal funding is so limited and hard to come up with in these straitened economic times. On the other hand, if you get the fellowship you will be getting funded for doing exactly what you are supposed to be doing in the summer as a graduate student: research. So if you feel like the faculty you've spoken to are not helping you enough with this, it could be worthwhile to discuss this with someone like the graduate coordinator or department head: not in a way which casts any blame on the faculty members, but just to emphasize that you want to do this very desirable thing and you haven't yet found the right person to help you out.