My friend did this and she moved to the Capital Hill area and got random roommates. She waitressed for a restaurant on the Hill and went to happy hours on the Hill. Eventually she met enough people and finally got some interviews. But it took 6-9 months. Also check out jobs on ohmygov.com – there’s some hidden ones.
The only other advice is to go to your university alumni events. Also check with the alumni association to see if they have a database/Facebook group/LinkedIn/Yahoo listserv where you can find grads in the area.