What you need to know
We're no experts at this, and we hope our lack of preparation doesn't come back to bite us at some border crossing in the future, but we'll give you a quick idea of what we've learned and the preparation we did do, and we'll be updating this when we know more about it. One caveat: we're from the USA (and Claudia also has Italian citizenship), so what applies to us may not apply to you if you hold citizenship somewhere else. Travelers from the USA have to pay notoriously high visa rates, often as reciprocity for high rates that we charge foreigners to enter the US. Also, this stuff is constantly changing, so don't trust our word. Be sure to call the embassy/consulate for the latest information.
A visa is a stamp or a small slip of paper which is attached to your passport allowing you to enter a particular country and stay there for a limited amount of time. It's a small piece of paper that can be very expensive. There are different types of visas, depending on whether you're just visiting the country you're trying to enter, you want to live there temporarily, you want to study there, you want to work there, etc. We'll be dealing exclusively with tourist visas.
There are two reasons to do research on visas before showing up at a border/airport: first, some countries do not issue visas at the border or airport, instead requiring that you have obtained one in your home country or at an embassy abroad prior to showing up at their doorstep; second, some countries have stringent requirements, from forcing you to pay for the visa in US Dollars to forcing you to show proof of onward travel. It seems that countries which fall into the first category are quite strict about this rule, yet are fairly rare. The second kind of country is more common, but their requirements and the possibility of getting around them seems a much more complicated situation.
Before the trip, from advice from friends and other seasoned travelers, some research on the US State Department's website, and those of many countries' US embassies, we targeted India and Bolivia as the only countries which may require visas in advance. India's process was quite easy; living in DC is definitely a plus in this respect, as you can apply for visas in person. I won't detail all the steps, but two hours of paperwork and gathering materials, and two trips to a private visa-issuing office in Georgetown and we now have 10-year access to this country. All of India's visas are handled by Travisa Outsourcing, whose website contains all the information you need to know. Bolivia proved a bit more troubling, as they required detailed travel plans, as well as proof of onward travel. Since we're planning on busing in on an unknown date, busing out on an unknown date and at an unknown location, and staying in unknown hotels and hostels along the way, their requirements weren't really a possibility. See below for what we ended up doing.
As far as countries with strange requirements for obtaining a visa, especially proof of onward travel, advice from friends, fellow travelers, and books we've read ranges from "If you have an American passport and a major credit card (showing that you have the monetary means to leave the country), there won't be any problem" to "A $20 bill goes a long way to changing the mind of an uncooperative border agent" to "there's no way around it; you won't get in without the exact requirements". The sense we get is that the rules depend very much on the border you happen to be at, the time of day, your mode of transportation, and the agent you happen to be dealing with (as well as how much sleep he or she got, the last time he or she ate, whether or not he or she had a fight with his or her spouse). We're trying to be as prepared as possible, reading up on the requirements, making phone calls, listening to the experiences of other travelers, and we also have the advantage of a loose timeline and itinerary. If we get turned away at a border, we can always stay nearby for a few days trying to gather the required information, or just try again a few days later, or find another way into or around the country.
Here are more details on the countries we've visited or somehow know something more about. Once again, your mileage may vary; be sure to call the embassy for the latest information.
We were forced by a ticket agent at Spirit Airlines at Washington's DCA airport to show proof of onward travel, but nobody else we met in Colombia had a similar experience, using either the land borders or flying in directly. Since we were planning on busing from Colombia to Ecuador, we did not have proof of onward travel, so we bought a refundable plane ticket from Colombia to Ecuador at the airport from our computer so that Spirit would let us board our flight to Colombia. We ended up canceling this plane ticket (losing only $25 each in fees) and took a bus to the border and walked across the border to Ecuador with no problems. No visa is required for a stay of less than 90 days in Colombia.
We used the Ipiales (Colombia)-Tulcán (Ecuador) crossing from Colombia and had no problems except a long and inordinately slow-moving line. No visa is required for a stay of less than 90 days in Ecuador. Note that the Galapagos have a separate system of psuedo-immigration, which costs $110. (You can even get a Galapagos stamp in your passport!)
We used the Macará (Ecuador)-La Tina (Peru) crossing from Ecuador (in the middle of the night). Everything went smoothly and easily. No visa is required for a stay of up to 90 days.
Bolivia requires US citizens to get a visa. Information we had gathered from our guidebook, websites, and countless phone calls to various Bolivian consulates was a bit conflicting, so we were not 100% sure we'd be able to show up at the border crossing in Desaguadero and acquire a visa. Since Nick only has a US passport, we decided it would be prudent to get him a visa ahead of time, in case we couldn't get it at the border, because we didn't want to deal with getting turned away at the border and having to go back to the closest Peruvian town with a Bolivian consulate. We found out there was a Bolivian consulate in Cusco, our last stop in Peru before heading to Bolivia, so we went there with all the required paperwork (photocopies of passport, proof of yellow fever vaccination, credit card, itinerary and reservations; visa application form; $135 US in exact change) and they issued Nick's visa in about an hour. Claudia is an Italian citizen as well as US, and Bolivia does not require Italians to have a visa, so upon entering Bolivia in Desaguadero, she showed her Italian passport. However, she had used her US passport in Peru, so the Bolivian immigration police insisted that she enter Bolivia as a US citizen, and therefore she needed to get a visa. (By the way, this type of thing has never been a problem in the past.) After a few nervous moments, getting Claudia a visa at the border proved to be easier than getting one in Cusco: all they asked for was $135 (which we luckily had on us or we would have been in trouble!) and the visa form, which they provided. Phew!
No visa required for 90-day visit. Probably our easiest border crossing yet from Villazon, Bolivia to La Cueca, Argentina. Short lines on both sides and, surprisingly, not even a form to fill out to enter Argentina.
No visa required for a 90-day stay, though we were asked for proof of onward travel. Greyhound sells cross-border bus tickets online, and we've heard they allow changes to the ticket for no charge except the difference in price. We bought a ticket from Nelspruit, South Africa to Maputo, Mozambique that we'll probably end up using.
Visa required. They are available at the border, but at the consulate, they told us that most buses require you to have one in advance so that they don't have to wait. We obtained sixty day, double entry visas from the consulate in Cape Town. It cost $94 for Nick as a US citizen and $68 for Claudia as an Italian citizen, and took 24 hours. Two passport pictures and some details about your itinerary are required.
We entered Malawi from Mozambique overland via the Zóbuè border. Visas are not necessary for Malawi for many people, including US and EU citizens. Entry is granted for 30 days. Formalities were quick and straightforward. Proof of onward travel and yellow fever vaccination were not asked for.
We entered Tanzania from Malawi overland at the Songwe border. Visas are required for Tanzania for most people. US citizens must pay $100 (multiple entry for 5 months) and EU citizens are charged $50 (multiple entry but only from neighboring countries for 3 months). Proof of onward travel was not asked for (even though we had heard it might be) but yellow fever vaccination was. Visas must be paid for in US Dollars. Formalities were quick and straightforward.
Most foreigners, including Americans and Europeans, need a visa to enter Uganda. We arrived via airplane at the country's only international airport, Entebbe. Visas can be easily attained at land borders and the Entebbe airport upon arrival for $50 (payable in USD only) per person and lasts up to 90 days.
Obtained 10-year multiple entry visas in advance from Travisa Outsourcing in Washington DC at a cost of $166 per person.
Nepal visas can be obtained in advance but are very easy to get at the airport upon arrival. We flew into Kathmandu from Delhi (India) and purchased our visas on arrival at the airport. Everyone is charged the same fee, regardless of nationality: 15-day visas cost $25, 30-day visas cost $40, and 90-day visas cost $100. One passport photo and USD for payment are required. Proof of onward travel was not required.
No visa is necessary for travelers from the US, and most other countries. 30-day entry stamps are issued free of charge at the airport (but you only get 15 days when entering overland).
Visa-on-arrival is currently not available in Myanmar, but this situation will likely change in the future. We obtained our visas in advance at the Myanmar Embassy in Kathmandu (Nepal). The cost was $20, payable in perfect USD only, proof of onward travel was not required, and length of allowable stay was for 28 days.
Entered from Thailand via the Aranya Prathet / Poipet crossing en route to Siem Reap. We obtained 30 day visas on arrival for $20 USD (although the official tried to extort a bit of Baht as well. Be firm that the rate is only $20 USD). Two passport photos were required, but no onward travel or other complications.
Entered from Cambodia at the Trapaeng Kriel / Nong Khiang crossing. Obtained 30 day visas on arrival for $40 USD and two passport photos.
Entered Vietnam by air from Luang Prabang. Visas on arrival are available for an additional fee you pre-arrange it and are entering by air. We obtained ours in advance in Phnom Penh for $45 USD (though we hear it's the cheapest in Sihanoukville).
Processing took one day and required one passport photo.
No visa is required for US (or EU) citizens. Border formalities in Rome's Fiumicino airport were nearly non-existent, although we were asked about onward travel by the ticket agent when leaving Hanoi, Vietnam. We answered by explaining our plans confidently and were not required to provide any proof.