How should release notes be written?

Public release notes should contain at least:

• release, buildnumber
• all fixed public bugs
• all added public features

QA release notes should contain at least:

• release, buildnumber
• all fixed bugs including bug number
• all added features including links to design docs

Consider your audience and try to think what they need.

An other thing to add is new or discontinued support for certain platforms. (For example we quit support for Win3.1 and added Vista 64 bit).

I would take a look at the release notes of popular F/OSS projects:

• Firefox
• GIMP
• Ubuntu
• Android
• TeamCity
• etc.

All these projects have pretty readable and balanced release notes.

If you have an project-management/issue-tracking system, you should definitely be using that to generate your release notes. Trac and Redmine in particular are very good at this.

Release points should have a few properties, IMO:

• Remember your audience. If this is an iPhone app, few are going to care about the fact that a particular logic error on line 572 in the Foo class was fixed. But they'll care a lot about "app is now accelerometer-sensitive".
• Summarize the new developments, features, and bugfixes in a broad, sweeping way if possible. If you can tie these together thematically (e.g. "we implemented generics and anonymous types"), a short blurb about that is a good way to give people the big picture.
• Itemize the specific things that were fixed, with links to your public bug-tracker, if any. This can usually be automatically generated.
• Don't provide excruciating detail. One- or two-liner summaries of each thing that was added or fixed should be sufficient.
• Always include specific release identifiers (e.g. "v.1.4.5"), as appropriate.