A single PBP doesn't need all that many players, so "advertising" may not be the best approach. First consider all the techniques already listed on this site at Where can I find other RPG players? Even if the game is online, it might be nice to have friends, acquaintances, or even just people from your area in it. Here's an example of someone using meetup.com to advertise for a Demon: The Fallen PBP in the Denver area. This has the additional benefit of maybe turning into real tabletop at some point.
Also consider whether you really need to host your own PBP. There are a lot of PBP sites (and forums) out there already, like rpgcrossing.com and rpgm.com, and so PBPs on them are somewhat more self-advertising. Most are free and are simply forum-driven.
Speaking of forums - forums are still the #1 kind of site used by gamers. As a result pretty much every large RPG forum - rpg.net, enworld.org, etc. have places to advertise for games both in person and pbp, and often just run pbp there on the forums as well. Most every RPG publisher has a forum as well, and most will have dedicated subforums to these as well or at least be friendly to them in a general announcements subforum.
RPOL.net is for online forum gaming, but they do have an Offsite Gaming forum where they allow posts for other PBPs.