リンクファームなど検索エンジンSPAMと高い確率で取られるような方法は除きます。
Yahoo!などのカテゴリに登録するといった一般に広く認知されている方法も含めて大丈夫です。
確かに、(はてななら)ホッテントリ入りすればブログとかで取り上げてもらえそうですね!
個人的にはmixiとかのSNSのコミュニティが結構有効だと思います。
プロフにさりげなくサイトのリンク入れておいて、自分が強い分野のコミュの質問スレなどで有益な回答を提供するとか。
頻繁にSNSしてる人の中には、別にブログ持ってる人も結構多いので。
でも、やりすぎて炎上しないよう注意は必要です。
大抵のSNSはクローズド型なので考慮してませんでしたが、口コミのハブとして考えると有益そうですね。
MLに流すメールの署名にリンクをつける作戦にちょっと似てますねw
すぐに被リンクに繋がるとは限りませんが、ソーシャルブックマークやSNS、ブログ、ストリーミングサービスを活用して客を呼び込む。
コンテンツが悪ければ見向きもされませんが、そこそこ面白いものが含まれていて頻繁に新しい情報が配信されていれば、ソーシャルメディア上で話題になって被リンクが一時的だとしても激増する事があります。