I got my current employment being introduced by someone inside. I found my previous company via job website, here are two that I find most helpful:
Obtaining residence: my current visa is (quite long): "Engineer/Specialist in Humanities/ Int'l Services" (技術・人文知識・国際業務) I got this visa sponsored by my first company, which is the most common thing for foreigners. Mine is 5 years, some are just a year long. It all depends on the company and how they file your paperwork.
I don't have permanent residency. I could switch over to spousal visa, but since I still have a lot of time left with my visa, I'm not going to bother the bureaucracy. Also, getting residency isn't as easy; it's like a point system here: how long you've been working, if you went to school in Japan, JLPT (Japanese Language Proficiency Test), etc.
Guarantor is only necessary for renting apartments (from my experience).