I was doing a bit of reading up on how to get a visa on arrival for Vietnam, and several sources mention that I need to get an "Approval Letter" to pick up my visa at the airport.
What is an "Approval Letter", and how do I get one?
A VOA for Vietnam requires that your visa request be pre-approved by the government before you travel. The "Approval Letter" is the document the government will issue once it has approved your request for a visa.
To get a VOA it is easiest to ask the tour company you are traveling with to organize the VOA on your behalf. There are also some agencies in Vietnam that will organize VOAs for any independent traveler for a fee. If you are going the visa agency route, you might do well to do a bit of research on travel forums like TripAdvisor, Thorn Tree, etc for recommended companies, as there are dodgy ones out there as well.
The process is pretty straight forward, you supply the usual personal factoids (dob, full name, passport number, citizenship, etc), pay the agency their handling fee & they apply on your behalf, you then print out the Authorization Letter they send you, find the VOA office/line upon arrival, hang around for a while as the officials take their darn sweet time processing you and then go be the last person to claim their luggage and start your adventure.
Depending on the tour company, some can arrange for your guide to meet you inside immigration and help speed up the process, but most leave on your own to handle the VOA process at the airport.