Well, the cheapest way (free), is to find other people who make games and ask if you want to trade links - you'll put their link on your site if they'll put your link on their site. Search engines like Google and Lycos are always willing to add to their database, as are software sites like ZDNet and Tucows.
If you've got cash to spend, you can always pay for banners on select sites. However, this isn't really a viable option for the hobbyist programmer.
The last option is to contact me again in a few months time - the game I'm making at the moment will have most of it's levels set in futuristic cities. In true Syndicate-style, there will be billboards and flashing displays dotted around. If you want to save me the job of making one more advert to put on them, send me yours!
"I am a living, thinking entity who was created in the sea of information."