Affiliate network fees are high for the larger networks. I work with clients in both Google Affiliate Network and Commission Junction, and know first hand what the fee's are and what it takes in sales to cover them.
I would suggest looking at http://zferral.com/ they are cheap and you can setup your own affiliate program. If you are already setup with an affiliate application then, create a page on your site which goes over the program.
Optimize the page's meta tags content etc to be "Product X affiliate program" or similar. See who's already ranking for the terms you'd optimize for and build a page with roughly the same amount of content.
Link to the page from the footer of your site. If you can add a banner to the home page promoting the program once in a while go for it. There are also affiliate directories where you can add your program to. Directories where people browse affiliate programs to sign up for. "affiliate program directory" is a good search term, one site is http://www.jamaffiliates.com/directory/
IF you or your client have access to the products or services directly that you offer on your website and have a good profit margin, I would contact competing sites and offer to drop ship or expand their line of products. Only if you know for sure you can sell them products or services cheaper.