When it comes to open source work, which I mostly do on my own, limited time and don't get paid for, I have a choice. I can spend time writing code or writing documentation. The former I enjoy very much, the latter I don't like at all. Guess which I am going to pick. The times when I've actually ended up writing some docs, I don't think anyone has ever read them. And writing the docs is just the beginning, they have…
You can run the source through one of those automated documentation tools like doxygen. That does make a big difference.
I'd prioritise a simple getting started guide. It only has to be a page or so, but something that explains how to run the program, and achieve a few simple tasks. It's far easier to go from a simple case to a more complicated case than it is to go from nothing to even a simple case.
To pick on a specific project, Treetop http://treetop.rubyforge.org/ has a pretty detailed set of documentation (human-generated, not automated), but I found it quite hard to go from the abstract enumeration of its features to actual working code. So hard, in fact, that I wrote up an introduction to help others, and it's been a very popular page: http://po-ru.com/diary/getting-started-with-treetop/