Wheel's comment regarding ask for a link is something we have done with a slightly different approach.
On my personal aviation related website, I have some verbiage off in the lower home page area which reads ..
"Do you have a website in the aviation industry? We are always interested in linking with relevant sites in the pilot, air traffic, aircraft, & related market segments. Click here to request your link! "
That verbiage is hyperlinked to a form which receives all link requests. Sure, we get some linkspam. We toss those. But what this verbiage does for us is get indexed in the search engines. When a link builder then searches "aviation link request" or "aviation suggest link", our suggest link form comes up in the top five results. Then we get link requests and many of them turn into one way links that I can then decide to either ignore or reciprocate.
Just by announcing in the corner of your website that you are open to link requests (and you should provide a form to receive those requests or a link to your editor based link management software from there) it creates more linking opportunities for your site.
Yes, they will all not be PR9 .gov links but you will get some good ones. You might have to get 10 bad ones for each good one but it does work and what's best is that its passive (no major work on your part). You don't have to do anything except set it up and then sit and wait (like fishing).