With GearCity, I made a presskit.
Sent out 80 press releases with a press demo of the game. Was picked up by 5 or 6 indie game sites. Net result was a couple hundred page views. Couple comments. I will come back to this in a second.
My competition, who started exactly at the same time, and spent the last 6 years focused on graphics instead of gameplay did guerrilla marketing. IE posting on forums that share the same topic about their games, social media, youtube, twitter, all that jazz. They built up through this sort of method (Social Media/ On Topic Forum Spam/Word of Mouth/Pretty graphics) 10s of thousands of followers. A mention of my game by my competition to people complaining about lack of "Tycoon" features in their game sent me hundreds of users...
Note, both of these are before public demo's of the games came out. So with that in mind. The press is dead. Don't waste time dealing with any game press sites unless you are a AAA game or can directly talk to a writer there.
Sending out the press releases did do one good thing for me. One of the few people that did an article on our game hooked us up with my current publisher. At the time it was difficult to get into Steam, but having a publisher with catalog rights pretty much gives you a blanket pass onto Steam. Of course, the barrier of entry has greatly been reduced on Steam. So that's not really an Issue. Anyhoo, my publisher handles PR, media relations, bundles, keys, other distribution channels outside of Steam, etc. All that crap so I don't have to (Which it's pretty much just me on my project, so it helps.) They do some other stuff as well, but I won't mention it due to NDAs. They do take a cut of the sales though. So if you have good PR helpers, it might not be a good solution to go this route.
Back to the game. For about a year and a half I released public demos of my game, called open beta's. 25% of the game for free. From that and a couple of social media sites (facebook/twitter/indiedb(moddb) it just spread by word of mouth. My first build, v1.0 had about 120 downloads? The final Open Beta before Steam Early Access release had well over 3,000 downloads from various distributors. I found it a very good way to build a fan base as well test the game before it goes public.
From there you get your Steam release. The first week or two is a lot of work. You'll get flooded with youtube reviewers (legit and not,) Real websites (we were on Rock Paper Shotgun for instance.) and Users. Keep them happy above all, as they're the ones that will leave the reviews that matter on your Steam page (which in turn effects both viewers to your page and sales.)
In summation, it's a lot of word of mouth. Find out how to get your game in front as many people as possible and let them spread the word about it. Look for forum threads looking for similar games to a popular game that is the same genre as yours. Post there. Find reddit communities about that game genre and sub genre. Post there. Dig up some abandonware forum post with similar games and say "Hey folks look at my game which is similar to this game." Make sure everywhere has a link to a site, or demos for people to access! After that, it's just a matter of making a good game, that people want to keep playing.
Of course, my game isn't a good example, we've only got 15,000 sales according to my chart. But most of those are full price to 25% off sales, and it's an extremely niche game. I'm just pointing out how we got here. My publisher plans on a hard marketing push once we're done with Early Access.