A press release is self-defined, that is to say it is the act of releasing something to the press.
To actually be helpful, one needs to look at what a press outlet will consider to be appropriate information. Most newspapers are not interested in giving free advertising space, as this decreases the nice black number at the bottom of the page (or, increases the red one). Thus, the first piece of advice on sending a press release is to look into local (or more widespread, if you are important enough) press outlets and see what they are writing/talking/showing in their everyday existence. Look for normal events (this means buying multiple papers), not aberrations or one time happenings (such as a special interest story).
In example, small town papers are quite likely to have extensive "local happenings" pages, with the amount of space dedicated to events rising inversely with respect to price. A free or heavily subsidized paper, will be quite likely to have a large area or section dedicated to letting local businesses get the word out on events of interest to the public.
A word on what is interesting to the public: You probably aren't. A manager at a business will often forget that their limited-time reduced-price once-in-a-year deal-of-a-lifetime that absolutely can-not-be-missed! will be forgotten soon after the expiration date on the coupon rolls around. That is what the advertising space that makes the Sunday paper difficult to handle existence is dedicated to getting across, and the community pages are not. If you are non-profit (not the same as for-loss), affiliated with the arts or music, or are occupying public space then you can probably get listed.
To contact the news outlet, scan the area that you hope to be shown in soon (You did investigate the paper, didn't you? If not, start over), and try to find the contact information listed there. If it is not listed, scan the rest of the paper for alternate modes of contact (not the letters to the editor). A general email address needs to have the relevant information in the subject line if you wish to have it acted on in a speedy manner. In other words, follow the general rules of etiquette. Be formal, but not stuffy.
If a phone number or regular letter address is given, follow up on that information. Take notes on your contacts, and try to get the name and extension of the fellow or lady who regularly pens the section you are trying to infiltrate. Make him or her your regular contact, and make sure you follow up on your half of any bargains that you strike. The person assigned to these duties is quite often just starting, and has quite a lot of duties to attend to regularly. Making their life easier by generating concise but effective prose will be appreciated, along with making the information that you consider important more likely to be printed. A half page of information will probably be cut down to a paragraph, and who knows what will make the cut?
Give times, dates, places, sponsors, and performers. Make sure you give prices or alterations from normal behavior. A brief biography of the performers or artist is good, but make it so that it can be cut and the rest of the release not be neutered. And remember the pyramid style of writing!
Be proactive in following up on leads. Do not assume that the reporter will put you in their Rolodex, or even care if you do not call the next week. If you want it done, do it yourself.
And now you are ready to let the world know about your little brother's band's preformance being held in your driveway next week! | 
