Here are two self-promotion items that Lyda missed that I consider to be very useful.
Business Cards The same printer that Lyda mentioned for postcards does really nice full color double sided business cards for a under a hundred bucks per 1,000. I do both sides as book covers with added info. Since a book cover is not quite the same shape as a business card this involves a good graphics program, an hour or two of work, and some swearing. But the end result is a very nice, very professional, card with my website, and release or buying information for the book.
I do a fair amount of travel, and I'm an extrovert. This means I meet new people on a pretty regular basis. Over the past nine months I've probably given four hundred cards away to people who've expressed an interest in my work. Another four hundred have gone out via friends or con goodie tables. Some of them got stuck to magnets, and I've got maybe a hundred left. When they run out, I'll order more. I'm currently hoping they last until I get the Cybermancy cover so I can do WebMage on one side and Cybermancy on the other for the next batch.
Book Store Visits I'm not talking about signings here, just making contact with the people who sell the books. As I said, I travel. Whenever I'm in a new city or town, I look up bookstores and stop in to say hello to the clerks and managers and to sign stock. Bookstores are your life's blood as an author. And generally, if you're good to them, they'll be good to you.
An aside on pacing and hair-tearing: I've said this before, but it probably bears repeating. I am thoroughly unconvinced of the efficacy of most self-promotion. Unlike Lyda, I'm relatively comfortable with the idea that once my books have gone to press there's not much more I can do about sales. I'm not thrilled by the idea, but believing I really could do something about it would result in the pacing and hair-tearing she talks about in her post below. This doesn't make me right and her wrong, or vice-versa. It also doesn't confer any moral or other kind of superiority on either position. What it says is that different writers maintain sanity in different ways, and that you need to find what works for you.
So, if doing little-to-no self-promotion is what makes it easiest for you to sleep at night and to get the next book done, do that.
If you want to do some promotion, figure out what sounds like it would work with your budget, both in terms of time and money, and do that.
If you feel the need to do a lot of promotion, and that'll keep you working and sane, do it.
So, the stuff I do: Cons. Cards. Visits. A few signings/readings. Media contact, interviews, articles, etc. If I didn't genuinely enjoy them, I'd probably drop the cons, the signings, and the media stuff. But I have a blast doing those things, so it's a twofer, maybe helping my career, and definitely helping my mood. So far it's working, my sales are good, and so are my reviews. Unfortunately, there's no way of telling whether they'd be worse or better if I didn't do any of this stuff.