While it isn't the most important thing to do before sending off a story (that's reserved for writing the story itself), drafting an effective cover letter/email is probably right below it.
So here is a quick sample of what to do and NOT when putting together a cover letter to go with your story. That being said, remember that I'm just one of many (many) editors out there, each with their own quirks and buttons to push. Like writing the story itself, practice and sensitivity is will teach you a lot, but this will give you a start.
So ... Don't Do What Bad Johnny Don't Does:
Dear M. (1),
Here is my story (2) for your collection (3), it's about a guy and a girl who fall in love on the Titanic (4). I haven't written anything like this before (5), but your book looked easy enough to get into (6). My friends say I'm pretty creative (7). Please fill out and send back the enclosed postcard (8). If I have not heard from you in two months (9) I will consider this story rejected and send it somewhere else (10). I am also sending this story to other people. If they want it, I'll write to let you know (11).
I noticed that your guidelines say First North American Serial rights. What's that (12)? If I don't have all rights then I do not want you to use my story (13).
I work at the DMV (14) and have three cats named Mumbles, Blotchy and Kismet (15).
Mistress Divine (16)
(1) Don't be cute. If you don't know the editor's name, or first name, or if the name is real or a pseudonym, just say "Hello" or "Editor" or somesuch.
(2) Answer the basic questions up front: how long is the story, is it original or a reprint, what's the title?
(3) What book are you submitting to? Editors often have more than one open at any time and it can get very confusing. Also, try and know what the hell you're talking about: a 'collection' is a book of short stories by one author, an 'anthology' is a book of short stories by multiple authors. Demonstrate that you know what you're submitting to.
(4) You don't need to spell out the plot, but this raises another issue: don't submit inappropriate stories. If this submission was to a gay or lesbian book, it would result in an instant rejection and a ticked-off editor.
(5) The story might be great, but this already has you pegged as a twit. If you haven't been published before don't say anything, but if you have then DEFINITELY say so, making sure to note what kind of markets you've been in (anthology, novel, website and so forth). Don't assume the editor has heard of where you've been or who you are, either. Too often I get stories from people who list a litany of previous publications that I've never heard of. Not that I need to, but when they make them sound like I should it just makes them sound arrogant. Which is not a good thing.
(6) Gee, thanks so much. Loser.
(7) Friends, lovers, Significant Others and so forth -- who cares?