The main current answer is spot on regarding visa types, but explicitly says that the author doesn't know the small liberal arts college (SLAC) environment. I am a math professor at a SLAC. We have hired many international faculty members over the years. The normal thing is to hire directly after finishing a PhD, and such professors usually start on their OPT. If they are on the tenure track, then we (the university has an office for this) get them an H1B visa, and eventually a green card. I know several people who went through this process, in several different departments. Normally, for a visiting assistant professor (VAP) we don't sponsor an H1B visa, probably due to the cost and due to the large number of applicants we get who do not need such a sponsorship. However, everything is negotiable, and I can easily imagine a situation (e.g., a computer science professor) getting such a sponsorship if there was a big demand for the courses they could teach, and not so many good applicants in the applicant pool.
Lastly, it is MUCH easier to get a job at a SLAC if you are already in the country. Even for a VAP job, we want an on-campus interview, to know that you can teach. It's highly unlikely to fly someone in on an international flight for that. So, I'd say it's best to apply for jobs at SLACs in your last year as a PhD student, before you leave the US. Lastly, some R1 universities have mentorship programs designed to help PhD students who want to end up at a SLAC, e.g., OSU has the Preparing Future Faculty program.