That's a difficult one - we can see how hard Yahoo and Bing have tried against Google - it's hard to get mainstream users to change - maybe if DDG could be positioned to drive site search for some more mainstream sites so that when people searched they would see the DDG branding especially with a "web search" option in the site search results. There might be some wiggle room to move into the territory Yahoo BOSS was targeting now that it seems like that project is abandoned after the Bing deal.

From a psychological point of view I think they could be reached by ads which emphasize the DDG vs. Google privacy issues, but something brief such that they wouldn't need to spend more than a minute reading it.

I already do recommend DDG to people, especially those who I know that care about privacy a lot.

Link to it on facebook. If they see you as a reliable authority on tech things, they will take your suggestions seriously, and in some cases share them. I've had more than a couple links go mini-viral after I posted them.