If you can afford it, I think planning a trip to a prospective city and telling prospective employers that you will be in town for a certain set of days might substantively increase your chances of getting interviews and being considered for jobs. Some years ago I decided to move from a job just outside New York to the Detroit area (for family reasons -- why else would someone move to Detroit!). After sending many letters and resumes, I finally found a contracting agency willing to pay my airfare and expenses to come to Detroit for an interview. I let it be known that I would be in town, and suddenly I had two additional interviews and a total of three job offers after I returned home. I was in the happy position of choosing between competing offers, which is always a good thing. :)

This has the added benefit of giving you some exposure to the prospective new city before you make a decision to move. For example, many Californians have trouble adjusting to the weather patterns here in Seattle, and average home prices now exceed $400,000 in King County (admittedly, this is a far cry from $700,000). You might find that other locations may not meet your expectations.

I entirely agree with other advice you have received with respect to contract employment. Nearly every job I've taken has started as a contracting position, including the one I'm working in now. Contracting is a great way to 'try before you buy' both for the employer and for the employee.

I've also been very pleased with LinkedIn as a networking tool.