Scrivener. I can't recommend it highly enough.
I did try StoryMill first, but I didn't really 'get' it. It seemed to have a learning curve, or an ideal way it was 'supposed' to be used that I couldn't figure out. It put too many tools, widgets, and whatsits in my face and made me feel like I oughta be using them. So I tried Scrivener, and it just worked for me, no distractions, no trying to figure things out, I can just start writing and all the tools I need are there when I need them. From memory, the free trial for Scrivener has extremely generous terms, so that you can give it a REALLY good try out before making your decision. (I ponied up the $$$ long before my free trial expired, and I haven't so much as opened StoryMill since the day I transferred my work from it.)
Scrivener 2 came out recently. I haven't upgraded; I'm still happy with the old version. The new version brings a lot of new features, though, including a reasonably straightforward way to sync with an iPad, character name generators, more sophisticated goals and deadlines tracking and the like.
I guess the question is, what do you want/need from writing software? What are you hoping to get out of it--what features do you need that aren't in, say, TextEdit? Having a clear idea what you're looking for should help you identify the right software choice for you and the way you write.