Think of it this way: as classical liberals, we understand that a bureaucrat in Washington could not possibly have enough information to correctly regulate the price or quantity of a good or service. This applies to labor markets, and immigration is essentially a function thereof. There's no way Washington or the state of Arizona can know how much immigration we really need.
Only the free and voluntary interaction of people and enterprises in an unfettered market will result in the "right" amount of immigration to our country (that is to say- the amount which will result in maximum productivity and value for all parties involved). I actually believe however, that we are seeing more immigration than a free market would produce because of other policies that create market distortions.
So to completely leave the matter up to the marketplace, we need to grant amnesty, end quotas and limits on immigration, and end the nightmarish bureaucratic processes for getting into the country. But we also need to stop allowing non-citizens to take advantage of Federal and state entitlements (frankly we need to stop citizens from doing so too), and we need to stop fixing the price of labor so artificially high, which encourages businesses to hire market-priced labor on the black market (i.e. "illegal" immigrants who are willing to violate the government-enforced cartel on labor)- e.g. end minimum wage and legally-required employment benefits.
Why amnesty? Because it's a dumb law. Locking people up for no other reason than they don't want to be documented isn't very enlightened, moral, or nice. When the government wants to start documenting you and making you walk around with a National ID (which they'll do on the basis of controlling illegal immigration), how will you feel about it then? Anytime the government starts saying: "Papers please," it makes me nervous as a libertarian and a casual observer of history- particularly recent German history if you know what I mean. If we pass a bill in 2013 to repeal the individual healthcare mandate- you would support amnesty for people who didn't comply right? Because it was a stupid law, right? I think immigration is the same way.
As for non-economic effects of immigration, which people always love to bring up- so what? Okay, they're changing our culture and speaking a different language. No one is forcing you to speak any language that you don't want to speak or practice a culture you don't want to practice. If you are truly loathe to deal with people who speak broken English, then don't bother with them or patronize businesses that employ them. Just don't use the force of government to punish private businesses who disagree with your choice and want to make their own decision. And just what are Latin immigrants doing that is so horrible for our culture? Is it because most of them have a strong work ethic, solid family values, and deep respect for God and religion? What conservative wouldn't like to see more of such people in our country?
Finally, our public safety should always be a paramount concern. While we should not punish all immigrants (by restricting their access to our country) just because some commit crimes (after all, some American citizens commit crimes too), we should deport the ones that commit violent crimes- including DUIs. Instead, our politically-correct sycophancy often allows dangerous people to remain in our country and commit more violent crimes.In the end, the free flow of people, goods, ideas, and capital across borders should be every libertarian's dream. It increases our productive possibilities and makes our nation strong. People come to America because America is great. The best, brightest, most productive people of other countries with less freedom than ours will not suffer their governments to punish them for their excellence, so they come here. Why wouldn't we want them here? Immigration is the sincerest form of flattery.