Please use Texinfo for documenting GNU programs. See the Texinfo manual, either the hardcopy or the version in the GNU Emacs Info subsystem (C-h i). See existing GNU Texinfo files (e.g. those under the `man/' directory in the GNU Emacs Distribution) for examples.
The title page of the manual should state the version of the program which the manual applies to. The Top node of the manual should also contain this information. If the manual is changing more frequently than or independent of the program, also state a version number for the manual in both of these places.
The manual should document all command-line arguments and all commands. It should give examples of their use. But don't organize the manual as a list of features. Instead, organize it by the concepts a user will have before reaching that point in the manual. Address the goals that a user will have in mind, and explain how to accomplish them.
In addition to its manual, the package should have a file named `NEWS' which contains a list of user-visible changes worth mentioning. In each new release, add items to the front of the file, and identify the version they pertain to. Don't discard old items. This way, a user upgrading from any previous version can see what is new.