I'm surprised you feel that way. I also work for a local newspaper, and a our largest demographic is the 55+ group. It seems like getting the facebookers (the under 30s) onto our site could really help.
That being said, I don't know how I'd do that, and we don't have facebook connect because the API is more effort than it's worth.
Make a Page, publish your stuff via RSS, start local Facebook conversations, ask people for local photos and for news of what's happening, possibly get them contributing ideas for stories. The more you can get people swept away into your cause, and that's not hard, then the more activity and attention and relevancy you've got.
Probably the most attention I've paid to a company beyond Facebook, Tumblr, and Reddit in these last few months has been to a clothing company with an excellent Facebook presence.
That being said, I don't know how I'd do that, and we don't have facebook connect because the API is more effort than it's worth.