Why User Stories?
Any software project needs a Business Requirements Document (BRD)—a document which describes what the deliverable is supposed to do once it's been built. The traditional (waterfall) way is to write it in paragraph form, but several agile development techniques recommend writing it in the form of a collection of "User Stories".
What is a "User Story"? A user story is not, in fact, a story at all—it is a description of the requirements for a particular feature of the product, broken out independent of all other features. The term was originally developed as part of the eXtreme Programming (XP) methodology. Kent Beck proposed that requirements consist of a collection of index cards, each with some notes describing a single feature of the system (e.g.: "Users can log in using name and password"). The card didn't have space to describe the requirement fully; it served as a reminder the team members about the conversation they had previously in which they discussed what was needed. Other agile techniques like Scrum have dropped the idea of using index cards (it turns out that having the full details in writing and sharable electronically is quite useful), but have retained the key idea: to express the requirements as a collection of individual "stories" which are user-meaningful features.
For the business analyst tasked with creating the BRD, the "user story" form is more difficult than the traditional paragraph form. It's not a matter of formatting (your word processor can handle this), or that the form is unfamiliar to users (true, but they get used to it very quickly); the difficult thing is to decompose the undifferentiated mass of customer needs into coherent, independent items. A BRD in paragraph form does not need to organize its content in any particular fashion—a requirement "counts" so long as it is mentioned anywhere in the document. But coalescing these into independent stories and decomposing them until they are a reasonable size requires additional effort.
"So What," you may ask, "is the benefit of user stories that justifies this additional effort?" The benefit is in flexibility and estimation. Flexibility, because (however much we may want to) it is almost never the case that we begin a project with a perfect understanding of what will be delivered in the end. Removing a feature part-way through the project may not save much time if the project was conceived as a monolithic whole: the implementation may already be half-complete or the feature may be entangled with other items so that there is little effort savings. But canceling a user story that hasn't yet been started does, indeed, save all of the effort for that story.
Estimation is also improved, not at first but over the course of the project. This is because the user stories can be assigned relative sizes in arbitrary units like "story points". As the project progresses, the actual effort required to complete a story point can be measured and used to refine the estimate of the overall project effort. The fundamental difference which makes re-estimation more accurate for projects broken into user stories than is possible for projects scoped monolithically is that during the development individual stories are implemented completely with a limited number in progress at any given time. This avoids the common problem of thinking "we're 90% done" then finding that the last 10% takes as long as the first 90 which normally makes mid-project re-estimations unduly optimistic.
So, when would one want use the "user story" approach to writing a BRD, and when would the traditional (paragraph) form be better? If the requirements for a project are particularly uncertain or the existing estimates are poor and need to be improved, then the flexibility and improved estimation will make the user story approach pay off. If the project's delivery date is quite firm but its scope is somewhat negotiable, then the user story approach helps to ensure there's something workable on the date even if the project runs behind schedule. On the other hand, if your project's scope is well-understood and unlikely to change then the extra business analyst effort needed to decompose it into stories may not pay off. And if you don't have available business analysts with experience at the user story approach (or at least with the willingness to learn) then it may be better to stick with a simpler approach to requirements.