Let's say I want to fly a private airplane to another country. How does one arrange such a flight? Of course this might vary between states, but in general do you need a special permit to fly in with a particular airplane, other than a permit to enter the country? Do you schedule a landing with the airport of destination?
It really depends on the laws of the country you are planning to flight to.
If you want to fly between states in the US, there is no requirement to do any paperwork. Federal Aviation Regulations allow you to fly any distance domestically without filing a flight plan, assuming you are flying under visual flight rule (don't need ATC service), and don't need to fly through any restricted airspaces (most of the US airspace isn't restricted).
Canadian laws require flight plans for all flights longer than 25 nautical miles. However, filing a flight plan doesn't necessarily involve paperwork. Most people do it over the phone.
Flying in Western Europe is similar, but since most airports in Europe require advanced notice (and payment of a landing fee), you'll also have to call the destination airport. Technically you can still fly anywhere you want without doing that... you just won't be able to land.
I don't know much about flying in Eastern Europe, Middle East, or Asia, though if you are in a place like China, where the entire national airspace is restricted and you need a clearance from the military for every take-off... I am guessing there will be paperwork involved.
If you are flying between US/Canada/Mexico, in addition to filing a flight plan (5-10 minutes), you'll also need to notify customs of the destination country so they can expect your arrival to clear you. That also just takes a short phone call.
If you are flying in/out of the US, you'll also need to file eAPIS (electronic advance passenger information system) online. Basically just have to give them names, day of birth, and passport numbers of everyone on the flight, and they will email you a preliminary clearance. You still have to clear customs normally once you land.