As a grad student, I have a single publication, a conference proceeding, to my name. So, my question is what do I need to do to obtain a post-doc position? Obviously, my references are going to be important. But, what other methods are available to me to demonstrate my competence? As I am US based, is it worth my time to apply for an NRC fellowship?
Obviously things vary from subfield to subfield, so canonical advice is probably to much to hope for. With that in mind, let me try to give you something of an answer.
In principle when a person finishes a PhD, if they remain in academia, there are a number of ways this might happen. They might end up with:
Now, (4) is essentially unheard of these days, so you can more or less forget that. Of the rest, what is feasible will depend on a number of factors, but the impact of your research is going to play a big role in your success in applying for either (2) or (3).
I presume, since you are only looking at what to apply for now, that you haven't finished the PhD yet, and have something on the order of six months to a year left (do correct me if I'm wrong). With this in mind, it seems quite possible that you'll have more than one publication by the end of the PhD. If this is possible, you should put in the effort to write up results. If you get 3 or 4 papers (preprints definitely count, so make sure you are using the arxiv and including them on your CV), this will substantially alter your odds of getting a postdoc from someone you haven't previously worked with.
Personal fellowships are the most sought after form of postdoc, as they usually allow substantial autonomy, and so provide something of a springboard for a research career. This means that they are competitive and realistically, I can't see someone getting one on a single publication. I was rejected from some of the ones I applied for with 8 publications including a number of PRLs.
Postdocs supported from someones grant are easier to get, but still competitive. If you have only one publication, it might prove hard to convince someone you don't already know of your potential, though it is perhaps still worth trying, especially if your paper is particularly interesting.
The best way to get a position if you are really limited on publications is as a postdoc on a grant supported by someone you have worked with before, or who knows your work well. These people are more likely to hire you on potential or other factors, rather than on your publication record. The scope for this is of course limited, so as Pieter points out the more people who know you and your work, the better.
That said, my advice would definitely be to start applying and get your results written up as soon as possible.
Probably it would be good to try to get people at other universities to know you. One way is by trying to give as many talks as possible, not only at big conferences but also at smaller colloquia. Many departments run a staff colloquium, you could try if you can give a talk there. If they don't know you yet, perhaps your advisor can suggest this to people (s)he knows.