Immigration and tenure track in the United States
I've taught at both large R1 universities and small liberal arts colleges. For the large R1s, we don't care -- we simply want the best person for the job, regardless of their nationality. R1s have very competent foreign scholar offices and lawyers who know how to do the proper visa paperwork.

At smaller schools, it's more difficult. Budgets are tighter and the provost has more say over searches. If there are two candidates that are almost equally ranked, then the provost may suggest one over the other for non-academic reasons. There may not even be approval for international airfare for job candidates at the interview stage. 

You have to remember that an H1B application will cost at least $10,00-$20,000 in lawyer's fees, staff time,  and application costs. The stack of paperwork for the Department of Labor certification itself is about 3 inches thick. Furthermore, even though there is an exemption, sometimes H1B applications can be very, very slow -- which means that an instructor hired in March might not be able to join the campus by August. This can be deadly for a small school that needs its faculty present.

tl;dr Be the absolute best candidate possible for the position and the visa status won't matter. Otherwise, it is a factor amongst other factors.