Search engines show PPC ads in their search results and advertisers only pay if someone clicks on the ads:
PPC ads, especially Google AdWords, can be a good way to get traffic to a new Web site until it begins to naturally rank through search engine optimization. If you don't believe that PPC advertising works, take a look at how much money the hostel booking engines are spending on PPC advertising (sample query).
A tutorial on how to get started with Google AdWords can be found here:
In some countries (like Japan), Yahoo has more users than Google.
There are some banner advertising programs that specifically target backpackers such as Hostelineurope.com Network (All over the World.). There are some banner advertising programs that specifically target backpackers such as Swuzzlebucket.com (New Zealand and Australia).