Create unique and interesting games that you're proud of (most important).
Make a variety of solid connections in a variety of networks; don't surround yourself with the same interlinked group. This will increase the probable reach of your game. Join, contribute to and participate in different communities (forums, subreddits, social networks, irc channels, real life meetups).
Don't just make sure people know your game exists; make sure they
really know it exists. I usually have to hear about something multiple times before I check it out
Don't
spam your stuff on social media. That's annoying and a sane person definitely won't follow you. Don't tweet because you want to market; tweet because you want to share your cool content. Try to make each tweet have different content (much easier while developing the game).
Have a presskit for your game. I hear journalists really like
presskit().
Contact journalists.
My advice, in addition to Steve's, is to start tweeting. Use the tags #gamedev and #indiedev. Every once in a while, one of the retweet robots will pick up on the tag and give you a free tweet to their thousands of followers.
Does that not happen
every time you use the #gamedev hashtag? I always, without fail, get retweeted by @gamedevrobot and @theindiesloth when I use it.