I'm learning this all myself so I'm no expert but:
Start early (long before game is finished) creating a buzz!!
Doing press releases can help.
Getting review sites to review your game.
Being active (and liked) on as many forums as possible is a very good thing.
Putting something in your game that allows people to follow you on twitter or post on facebook.
Also creating a facebook landing page is very good.
Here is a forum that's mainly for iPhone but may have some good info there:
Promoting techniques
A video series that is a must for anyone I think despite that it's geared towards iPhone is:
MoMo Chicago Video Series
I have no association with any of these, btw ...