For many businesses the customer base is already hanging out online on blogs, websites, and discussion forums related to its target niche market.
A quick search on the major search engines for each of the best keywords associated with your niche will produce several pages of potential partners. Each of these sites are potential partners for you to work with. These websites are the places where your future customers are already hanging out.
Once you have your list, it's time to start forming relationships with each of the targeted sites. Even if you only wind up working with one or two of the fifty sites you find, it will have been well worth the effort.
In some cases your only option to gain exposure on these target sites will be to purchase advertising, but in almost all cases there are other creative possibilities available to you. Begin an intentional campaign of attracting the attention of the key decision makers on these sites by contributing to their success and by expressing your desire to partner up. Here are some creative ideas to try: