I have tested with PPC, I think it is not effective. I tried to drive traffic to one of the tips article but there is no people submit their article.
Yes do press releases submissions, article submissions, seo and the best thing is blogging. Every business should have a blog with good linkbait style posts that your promote using social media sites like twitter, stubmleupon, digg, yahoo buzz etc.
I think you can try free r paid directories, link exchange, social bookmarking, press release, article submission, blog creation and submission, comments, participate to more forums, google & yahoo groups, yahoo answers ect. Hope it will help you out