I'm calling this "how to submit a short story" rather than "how to sell a short story" because I don't want anyone thinking I'm promising a magic bullet that will guarantee them success. There is no such magic bullet. (Except to write a brilliant and compelling story. If you don't think that's magic, then you haven't been paying attention.)
This is basic information, but here's my take on it anyway.
Every so often, you come across someone who seems to think they can skip this part. Editors, I'm afraid, are not interested in stories you haven't written yet. If you're an established and well-known writer you may get an editor saying "Would you like to write a story for my upcoming anthology of telepathic homosexual cat minstrel stories?," but if you fit into that category, you're probably not reading this essay.
Don't skip this one either. Accidentally leaving a typo in is not the end of the world, but you don't want to give your reader any excuse to reject your story that you can avoid.
Okay, so this is the real substance of this essay.
There are a number of websites out there which have collated this information for your use. My personal favorite is Ralan's Webstravaganza, because it's updated reliably and organizes the info in a useful way.
Go first to the "Semi- and Pro Markets." Yes, really. Frankly, I do not buy into the idea that you should start out sending your stories to markets that pay a pittance, or nothing at all, to get "exposure" before you start submitting to the bigger places. (I didn't, and it's worked pretty well for me.) You've got nothing to lose in sending to the bigger places but postage, printing costs, and a little bit of time. If your financial situation is such that you're having to pinch every penny, then this may not be the best approach, but in that case, I recommend going for markets that take e-subs anyway.
Peruse the listings. If you're writing fantasy, then see which markets have an "f" or "df" (dark fantasy) in their codes. Likewise for SF (sf) or horror (h). Whatever fits the description of your story. When you hit one that matches, click on the market name; that will take you either to a pop-up window on Ralan's site or to the magazine's actual guidelines page. Either one will provide you with more information, including tidbits that will help you narrow down whether your f is the kind of f they're looking for. Pay attention to these guidelines. Don't send in things they say explicitly that they don't like. Follow the word limits. Don't sim-sub if they don't like it (that's when you send one story to multiple markets at once); don't multi-sub if they don't like it (that's when you send multiple stories to one market at once).
Once you have a list of suitable candidates, which one do you send to first? That's personal choice. Maybe you want to start off with the places that take electronic subs, so you maybe won't have to pay for postage at all. Maybe you want to start off with the places that respond the quickest; you can check the guidelines for info on this, and then go to the Black Holes site to see what the response times really are. Maybe you want to start off with the markets that pay the best -- five cents a word is the minimum rate to be considered a "pro market," which has to do with membership criteria for the Science Fiction and Fantasy Writers of America, our professional writers' organization. Watch out for places that cap their pay; it's a legitimate practice, but if they pay five cents a word up to fifty dollars, then they're only paying pro rate on stories a thousand words long or less. Probably the best course of action is to start off with the places where you think your story is the most appropriate, but that can be hard to gauge.
They tell you that you should read the markets you're submitting to, and it's true. But personally, I've submitted to over three dozen different markets. I can't afford the time or money to subscribe to them all, and while I can and often do buy sample issues, it's still hard to know the tastes of all the editors. Another useful path is to read reviews of magazines; that can often help you get a sense of what the editor is looking for. And pay attention to your rejection letters when you get them -- if there are comments, those comments may give you clues for use in future aiming.
A submission packet should be a large envelope, large enough that you don't have to fold the papers to fit them inside, containing at minimum the following things:
The cover letter should be short and to the point. Address the editor by name if at all possible; you can get the appropriate name from the guidelines, usually. If it's a group of editors, then I tend to just say "Dear Editors." Tell them your story's title, genre, and approximate word count; round to the nearest hundred. List any other publication credits you have. Sales to non-paying markets won't count for much, but if you lack anything else to show, you may as well include them; I did. If your education is distinctly relevant (your story is a hard sf space travel story and you have a Ph.D. in astrophysics), then mention that. Thank them for considering your story, and sign off.
The story itself, if this is a snail-mail submission, should be in standard manuscript format. If this is an e-mail submission, it's usually either an attachment in SMF (often .rtf, sometimes .doc), or pasted into the body of the e-mail in what I've dubbed semi-standard electronic format. Sometimes it'll be an online form, taking either file uploads (SMF) or pasted text (SSEF). If the guidelines ask for something different than those standards, though, follow the guidelines. Always.
The SASE is for the reply. If you want your printout back, then include a large enough envelope with sufficient postage for the weight. This was common back in the days of typewriters, but with computers, there's not much point; it's easier to just print out a new one. I've never asked for a manuscript to be returned. If it's an international submission, some places will let you provide an e-mail address in your cover letter and they'll respond electronically. If not, then put in a self-addressed envelope and two International Reply Coupons, which you can get from the post office.
With snail subs, you may also want to include a self-addressed stamped postcard (you can buy cheap plain ones at the post office) that says something along the lines of "Please put this in the mail when you receive 'My Brilliant Story.'" It sucks to wait weeks and months and finally to query, only to discover the story never arrived at all. Not all places will open up the envelopes in advance and find and return those, though. Scifiction will, but at this point I've forgotten who else does, since I've fallen out of the habit of including such cards. Still, it can be handy. A lot of e-sub places have taken to sending you a message acknowledging that they got the story, which helps identify those e-mail glitches that can eat submissions.
Then, you wait.
Sometimes for a very long time.
As mentioned above, the Black Holes site can help you tell how long the market usually takes to respond, and to spot when new responses are coming in. You can also get information from The Rumor Mill, in the Rejection/Acceptance log. Other threads on the Rumor Mill will contain announcements if a market is backlogged and slow. Some magazines have websites that you can go to for information; they may even have message boards. All of these things can help you know how long you're likely to be waiting.
While you are waiting, I recommend making some kind of note that you sent Story A to Market M on such-and-such a date. This will help you when you have a lot of stories out there -- you are writing another one while you wait, right? Keeping good records means you'll notice when a story's been gone longer than it should be, and you'll be less likely to accidentally sim-sub or multi-sub, or to send a story to a given market more than once.
If the wait goes on for too long, you may want to query. How long is too long? Some places will ask you not to query before X time. Otherwise, I tend to go by the Black Holes data; I wait until I've passed most or all of the data points listed. It's a judgement call, as you don't want to annoy the editor by querying too soon, but you also don't want to wait forever. If you do query, then send an e-mail (most places will take e-mail queries, if not e-subs) to the appropriate address (obtained from the market's website) and say something polite like, "I submitted my story A to you on such-and-such a date. I have not yet heard back on it, and I was wondering whether it's still under consideration." Responses get lost sometimes, in physical or electronic mail; stories get lost sometimes, in editors' slush piles. Be nice, even if you've been waiting seventeen months and they supposedly respond in three. You may even have to send multiple queries. Give them time to respond to one before you send another. If they don't respond to the queries or the story, then eventually you may have to send another note saying that you're withdrawing the story, and then get it back on the road elsewhere.
Then you're in very large company. We all get rejected, generally more often than we get accepted.
First, the usual psychological caveats. They're not rejecting you; they're rejecting your story. It doesn't mean you're a failure as a person. It doesn't even mean your story is a failure. It may just not have been to their taste. If you got a personalized note, that's usually a good sign, since it means the editor put in a little bit of extra effort. Some of them do that all the time; others never do. Go to the Rumor Mill if you'd like to learn the fine art of rejectomancy, divining information from your rejection.
Either way, get the story back out there. Know where you're going to send it next, if it gets rejected where it's currently gone. Rinse and repeat, until you run out of pro markets to send it to -- you did start with the pro markets, right? There are some lesser-paying markets that are highly respected, and those are worth sending to early on, but on the whole, go for the places that will pay you more than a pittance. If you run out of those, then start looking at the places that only pay a token fee. Others would disagree with me on this, I'm sure, but it's my personal philosophy; I'm a professional writer, and that means I intend to make money from my craft. I can't do that if I'm only getting ten bucks for my story, in a magazine that hasn't built up industry clout by its publishing history and editorial acumen.
Every so often, take another look at the story, and see if you can improve it. Just because you went through Step Two doesn't mean you're done with it. Editorial comments or just your own improving craft may mean you have new changes to make. Some places will let you resubmit a story if you've significantly altered it; others won't. If they've requested a rewrite, then absolutely send it back, just as quick as you can.
It's a pretty simple process. My biggest recommendation is to be organized about it. Trust me -- when you have twenty-three stories out at twenty-three different markets, you'll be grateful for your notes.