Don't ever do paid ads, they won't work for small developers, especially not for very small teams with no budget (cost versus effect-issue) ...

Spread your game by making a (time-limited?) demo and upload it to the gazillion download portals out there. Release press info, write emails about your game to online magazines (be prepared for the fact that some magazines really don't give a [censsoreed] about your game and won't even respond).

It sometimes takes a while before things start rolling, but taken your game is mediocre or better, at least some increase of sales should be noticeable. Especially if you can "make others write about your game". According to some, even bad news is good news whatever the bad news, because it increases the overall publicity.

Cheers