AI War has been gathering a fair bit of publicity recently, and I've recently run up against the question of how one markets an indie game from several people. Well, the short answer is this: you do whatever you can.
That might sound flippant, but it's not. You use whatever tools you have available to you, and those tools are going to vary from developer to developer. If you have a big presence on Facebook, use that. Know a celebrity, or someone in the business already, or have some other sort of connection? Use that. If you've got some other sort of talent, that can make for other value-added content, use that.
Really, promoting an independent video game is very much like promoting a novel. If you google guides about promoting novels, you'll mostly find relevant advice (book tours and signings obviously don't apply, but all the rest does).
The Early Days
What about all those people without any special advantages, though? I mostly am in that category, as I had no special connections in the industry. Well, in these cases you are unfortunately reduced to the equivalent of "cold calling" potentially-interested parties (reviewers, distribution channels, bloggers, etc) until you start having some brand recognition or word starts getting out. This part of the process is very frustrating and slow, and you're likely to get very little if any response.
But. At some point some reviewer or distribution channel will hopefully find your brief pitch (like a query letter for a novel) to be of interest, and will take a look at the game. If they don't like it, don't expect much. If they like it or love it, then you've got your first bit of publicity (yay!). You need a ton more. So you keep sending out more missives to anyone you think might be interested, waiting on the existing ones, and sliding in a mention that so-and-so reviewer or distribution channel said [some quote] about the game. NB: Quotes from family, friends, and reviewers from sites the recipient has never heard of will actually hurt your credibility. Hopefully you can guess why.
Publicity Snowballs... Sometimes
Whenever a site of significant stature talks about your game or posts a link to it, other sites will pick up the story. This works to your advantage if the press you are receiving is positive; if the press is not positive, you are in trouble. If you're starting out as a no-name indie developer, you have to make a very good impression right from the start, and keep making that good impression on people as word spreads, or else you're not likely to get anywhere.
Bottom line: people want good indie games that are new and different, but they'll only talk about them if they are a certain amount in love with the product. If they just like the product okay, it's hard to get anyone excited enough to really talk much about it unless the job they do is reviewing indie games. To put it another way, if you want your indie game to get talked about outside the realm of indie gaming sites, your game has to be better than most, or at least have something notable about it.
Oh, and you have to actually put a lot of legwork into the publicity. And get lucky. There are quite a few indie games out there that are awesome, but which don't get the audience that they are really due. There are many other indie games out there that seem more successful than they really are. Since most indie developers (and indeed most AAA developers) don't talk about specific sales numbers in most cases, it's hard to know who is successful and who is not except for the really obvious cases. There are a few standouts at the top and the bottom, but otherwise it's all a big huddled mass of games and companies.
Success Is Relative
Word to the wise: most companies are not quite as successful as they seem to be on the surface. Just because a game is talked about on a major outlet does not mean it was financially successful. This applies to both AAA and indie games, from what I have read. It's a generally-accepted truth that most small businesses fail within their first year, and I don't think that there's much difference from that norm in the indie development business.
The catch? Most indie developers work in their spare time already, so if they aren't able to support themselves solely off of game development the company can still stay around. So the companies aren't failing and going bankrupt, but neither are they self-sufficient. Are there exceptions to this? Thank God, yes. There are a number of indie developers that are clearly successful, even ones that are not "darlings" of the industry. When I talk about "most indie games," I'm referring to some of the indie games you may have heard of, plus the thousands you didn't even know existed because either they are so poor, or so poorly-marketed, that they never break 100 or so sales. Lots of people think they can make a game, and a number of people try and create something, but then they either don't really finish it or they don't follow through with marketing, or both.
Word of mouth is invaluable to the indie developer. Having a positive buzz about your game is probably the only way to make it unless you get a publication contract. So this means, once again, exciting people beyond the "it's okay" stage. See the common theme here? Basically all the marketing in the world isn't going to help an indie developer if their product isn't worthwhile. It doesn't work for telemarketers, and it won't work for you.
Here's something else that generally doesn't work (as I've found out from experience, sadly): posting about your own game on message boards you aren't otherwise active in. You can't just register on some forum and pimp your game. I knew this going in, and so tried very hard to make a meaningful contribution to the forums in question while also mentioning my game. About 50% of the time people took offense anyway, and the other half of the time they were pleasantly surprised that I had actually contributed, but still not interested enough to click through and actually look at the links much. So learn from my early mistake, and don't put yourself through that sort of experience.
What does work is when fans of your game post on forums that they are active on, or other similar sites. But you can't control this, beyond getting people to the point of being excited about your game. If someone is talking about your game out on the Internet (Google Alerts to the rescue), you can definitely go join in -- people are generally quite happy to hear from the developer of a game they are discussing. You just can't roam around trying to start conversations about your own game.
As a new indie developer, you are selling yourself as much as you are selling your game. People need to know who your company is, what you stand for, and come to like/respect/trust you to the degree possible. Think about the creators of your favorite indie games, and most likely you know their distinctive "voice" from interviews, blog posts, magazine articles, or other coverage. You might even have a face to go with those names, if they happen to post pictures or have had some contest wins.
When people talk about PixelJunk, they talk about Dylan. When they talk about Braid, they talk about Jonathan Blow. The guys at 2D boy also get a fair bit of coverage as a company, as did the fellows at Introversion.
AAA games are made by giant companies, but indie games are made by individuals or very small teams. Players often want to know who the people are behind those games. If you want coverage and increased exposure, you need to write or say some stuff worth reading/hearing. The podcasts, interviews, and blogging that I do all contribute significant visibility to AI War and Arcen Games, and it's fun for me besides. I also try to visit most forums that talk about the game, to answer any questions I can and make sure people feel like I'm accessible if they need something.
If you don't like talking to people, you probably won't like being an indie developer. Unless you're exceptionally lucky or well-connected, you're going to have to talk to a lot of people about your game, your company, yourself, and whatever other topics are of interest. Hopefully you're like me and find this to be something of a perq, rather than a punishment.
At any rate, there ought to be something interesting about your game, otherwise you probably need to sit down and do some more work on it. Perhaps you've come up with some cool new game mechanic(s), maybe there are some technical innovations, maybe your art or music is extremely beautiful and amazing, maybe you're blazing new paths in storytelling or crossing game genres in unexpected ways, or maybe you have some sort of new control mechanic. Maybe you're doing something else that nobody ever thought of. Talk about whatever it is that makes your game unique, express your excitement, and enjoy talking with fans and potential fans.
Explore Every Opportunity
Note that I did not say take every opportunity. But, as your game gains in popularity, there will be a number of opportunities of questionable quality/legitimacy. Explore each one thoroughly until you are sure that it is not a good thing before you discard it. Sometimes huge opportunities come disguised as small notes or events that you might be tempted to write off.
Going along with this, this means that you should try to find all the reviewers you can to submit to, every distribution channel that you can find that is honest and willing to treat you fairly, and every other blogger or site that might lead to some promotion. Big boosts to visibility for your game can come from some rather surprising places, and often the places you thought would bring a lot of visibility really don't do much at all.
Provide Excellent Support
This one pretty much speaks for itself. Always be honest and open, don't try to hide your mistakes, and try to provide speedy resolutions to the inevitable issues that will occur (hopefully not too many such issues, though). Be open about timeframes and workloads, so that fans know what is going on. No one likes listening to a void, waiting for the next patch at some indeterminate future time (days, weeks, or months later? who knows?).
Basically: think of all the frustrating experiences you've had with support departments at big companies, and then do none of those things. Instead, just treat your customers like regular human beings, with all the due respect that implies, and you're pretty much good to go. Most customer service problems come about from being impersonal and distant, and/or making things overly difficult or treating customers like insignificant numbers in a queue. Just treat customers how you would want to be treated, and you're pretty well ahead of the game already.
Good customer service is a selling point, and besides which it's just the right thing to do. If you want people to be excited about your company and your games, good service is part of the package. Big companies take note!
You may notice, looking at this list, that a lot of the topics are only peripherally related to marketing. I didn't talk about magazine ads, banner ads, or any other sort of advertising. I didn't talk about exclusives or back room deals. Indie developers generally cannot afford this sort of thing, but that's okay -- there are other ways to succeed, it just takes longer.
At the end of the day, all you are able to do is create a product and then get some people to look at it. If they think it's great, they'll tell some other people and will enable you to tell yet more people about how great your product is with some degree of credibility. Great service, free updates, and other activities that make it clear you care about your customers are also a real plus.
But that's really all you can do. Keep sending out press releases, keep exploring every opportunitiy that you can find, but in the end you can't make people like your game. Never stray from the truth into hyperbole when discussing your product, because your credibility is a hugely valuable asset (and people don't fall for hyperbole very often, so you're wasting your breath, anyway -- there are solid practical reasons for being honest, aside from the moral reasons that are hopefully your main impetus).
If you make a great game, you still need to do a lot of promotion to actually find your audience. Even if your game is really great and fun, it's still going to be an uphill battle over an extended period of time. But if your game isn't great, no amount of promotion is going to save it. First focus on making the game everything it should be and more, and then focus on getting the word out. Neither task is easy, and both are equally neccessary if you want to do this as a business. Good luck!