this one's easy - depending on your budget (I'm assuming you have almost none but one never knows): Advertise in travel magazines, hit up some of the travel agencies that cater to your demographic, call some of the travel apps and website services to partner, hit up all the blogs in your space, combine that with a press release targeting the industry publications and reviewers ( it's actually pretty cheap to do - check out Marketwire or others like it). I'd probably also give some of the dating websites a shot - you might get some traction from sites that cater to singles and travel that way. Try the vacation clubs too - many of these cater to singles also - could offer them co-branding opportunities.

Given your demographic I'd also post in University/ College sites. When it comes to hostels/ bed and breakfasts, you can probably contact some of the industry organizations to get lists and partnership or advertising opportunities - and of course call up hostels in some of the bigger cities to have them put up a notice for you. Get a list of journalists that write for travel sites and magazines and send them an intro email - maybe you'll get lucky and be picked up by one or two, offer an exclusive interview if they pick it up ( and stick with your promise).

All of this is legwork, but (except for the advertising) it's pretty cheap to do - just a lot of salesmanship - which is laborious but I figure you have more enthusiasm than money.

Hope that helps - good luck!