Steelieblue, another option if your interested in saltwater fishing is to get hired on as a fish cutter or dockhand, spend a couple seasons doing this and acquiring sea-time and fishing experience, then enroll in a sea-school and obtain a captains license, I know 3 or 4 guys that have gone this route and found guide jobs shortly after getting licensed, usually by the resort/lodge they were already working for.

What part of the state are you moving to? if S.E. I can give you names and # of who to talk to and who to avoid.