There are things you are required to have by regulation and others that you should have, depending on where you are going. Here is a list to get you started:

AIRCRAFT EQUIPMENT

Aircraft Tow Bar

If you are going someplace that regularly handles your aircraft type, then maybe you don't need this. Otherwise, you should consider bringing one, or at least the tow head. Remember to consider all of your alternate, Equal Time Points (ETP), and Extended Operations (ETOPS) airports too.

Emergency Locator Transmitter (ELT)
An ELT is not specifically required by to fly oceanic, but you will find requirements for most operators in many locations around the world.

First-Aid Kit [ICAO Annex 6, Part II, Chapter 2.4, ¶2.4.2.2.]

Fire Extinguisher, Portable [ICAO Annex 6, Part II, Chapter 2.4, ¶2.4.2.2.]

Fuel Sample Kit
If your location will be dispensing fuel from 50-gal. drums or a fuel truck caked in rust, you may want a fuel sample kit.

Headphones, Microphones

High-Frequency Radios [AC 91-70B, ¶3-3.c.] [ICAO Annex 2, ¶3.6.5.1.]
You have Controller Pilot Data Link Communications (CPDLC) and SATCOM and both can be used to make position reports. But you still need an HF radio in controlled airspace when out of the range of VHF communications.

Life Rafts, Vests [AC 91-70B, ¶5-6.]
Make sure you have a sufficient quantity

Satcom
Satcom might be required in some regions when using CPDLC. 

SELCAL
Certainly not required, but nice to have.

Survival Equipment [AC 91-70B, ¶5-6]
Make sure it’s appropriate for the route.

VHF 8.33 kHz 
Required in various parts of Europe. [ICAO Doc 7030, Chapter EUR, ¶2.1.8.]

AIRCRAFT DOCUMENTATION
The documentation required for a trip will obviously vary by location and route of flight. Here are a few things you should consider for every trip:

Air Carrier Certificate (14 CFR 135 operations) [ICAO Annex 6, Part I, ¶4.2.1.1] 
An operator shall not engage in commercial air transport operations unless in possession of a valid air operator certificate issued by the state of the 0perator.

Aircraft Flight Manual and Systems Manuals [ICAO Annex 6, Part II, ¶2.4.2.2.]

Aircraft Noise Compliance Certificates [ICAO Annex 6, Part I, ¶6.13] 
An aeroplane shall carry a document attesting noise certification.

Aircraft Registration [AC 91-70B, ¶5.4.1.1.]
The advisory circular notes "a temporary registration certificate is not acceptable for international travel," but some countries will accept a "fly wire," or equivalent. You have to ask to find out.

Aircraft and Engine Logbook Copies [AC 91-70B, ¶5.4.1.1.]
The aircraft's most recent flight and aircraft log usually suffices, but some countries may require much more. Once again, you need to ask.

Airplane Flight Manual (AFM) [AC 91-70B, ¶5.4.1.1.]
Include weight and balance (W&B) information and metric conversion tables, if applicable 

Airworthiness Certificate [AC 91-70B, ¶5.4.1.1.]

Authorization Letters [AC 91-70B, ¶5.4.1.1.]
Not many countries require an authorization letter from the operating company or owner, but some do. If you aren't traveling with the person who owns the aircraft or is somehow identified on the registration, you might need to consider this.

Cargo Manifest, if applicable [AC 91-70B, ¶5.4.1.2.]

Certificates of Insurance [AC 91-70B, ¶5.4.1.1.] 
The operator is responsible for ensuring the need for airframe logbooks, engine logbooks and insurance certificates. For additional details for operations of corporate aircraft, contact the company’s aviation underwriter. In operations of private aircraft, if the owner is the pilot or is onboard the aircraft, there are usually no insurance difficulties. However, if a private aircraft owner is not onboard the aircraft, many countries require a letter from the owner that authorizes international flight in that specific country before they will allow operations within their country (you can find specific information on this letter and other requirements in the AIPs of the countries concerned).

Insurance paperwork can be problematic, it should be a question you ask prior to traveling any place new.

Customs Decals, Receipts [http://www.cbp.gov/xp/cgov/trade/basic_trade/uftd_info.xml] Decals are stickers that are placed on all private aircraft and private vessels (30 ft. or more in length) as proof that the user fee for entry into the U.S. has been paid for the calendar year. Any arriving vessel or aircraft that does not have an annual decal is required to pay a non-refundable per arrival user fee of $27.50, and complete an application, which will be forwarded to the processing center.

Import Papers for Aircraft of Foreign Manufacture [AC 91-70B, ¶5.4.1.1.]

Journey Logbook [ICAO Annex 6, Part II, Chapter 2.4, ¶2.4.2.2.]
This requirement comes from the 1944 Chicago Convention and is further explained in ICAO Annex 6, Part I and ICAO Annex 6, Part II. A journey logbook could be your aircraft flight and maintenance log, provided it contains all the necessary items.

LOAs/MSpecs/OpSpecs for Special Areas of Operation, if applicable [AC 91-70B, ¶5.4.1.1.]

Minimum Equipment List (MEL) [AC 91-70B, ¶5.4.1.1.]
If you operate internationally, you probably need an MEL and cannot get by with an MMEL. 

Navigation Charts [ICAO Annex 6, Part II, Chapter 2.4, ¶2.4.2.2.]
Include charts suitable for the route and divert location.

Passenger Manifest [AC 91-70B, ¶5.4.1.2.]

Radio Licenses [AC 91-70B, ¶5.4.1.1. and Chicago Convention, Article 29]
This is the aircraft radio station license.

OPERATIONAL APPROVALS
Depending on where you are flying, you may need:

Automatic Dependent Surveillance-Broadcast (ADS-B) Out
You can think of ADS-B Out as a higher-tech replacement of your transponder, it sends your GPS position and other data to ATC and other aircraft equipped with ADS-B In.

Where: It is becoming required in parts of the world, but work arounds are readily available. You can expect delays and reroutes if you are not equipped and authorized.

Authorization: is no longer required.

Automatic Dependent Surveillance-Contract (ADS-C)
You can think of ADS-C as a high tech form of "radar contact."

Where: Optional in much of the world's oceanic and remote regions, is also used domestically in various regions.

Authorization: 14 CFR 91: Letter of authorization required, 14 CFR 135: Operations specification required.

Basic Area Navigation (B-RNAV)
B-RNAV is not RNP-5 but the term has been "grandfathered" and will continue to mean the ± 5 nm standard without the performance monitoring requirements in a true Performance-Based Navigation standard.

Where: Most of Europe.

Authorization: Statement in AFM required.

Controller Pilot Data Link Communications (CPDLC)
You can think of CPDLC as a replacement for your HF when oceanic and VHF over some domestic areas. It is far superior to your HF and has distinct advantages over VHF.

Where: It’s optional in much of the world's oceanic and remote regions, is is also used domestically in various regions.

Authorization: 14 CFR 91: Letter of suthorization required, 14 CFR 135: Operations specification required.

Extended Operations (ETOPS)
ETOPS does not apply to 14 CFR 91 operators and only constrains 14 CFR 135 operators from flying in the most remote regions of the world. If you want to fly in those regions, the requirements are daunting and probably beyond what most corporate commercial operators want to do.

Where: Any place beyond 3 hrs. of a suitable airport with an engine failed.

Authorization: 14 CFR 135: Operations specification required.

High Latitude and Northern Domestic Airspace
Operating in what many simply call "polar ops" requires special certification under 14 CFR 135 and special procedures for anyone venturing the high latitude regions.

Where: High latitude operations occur in areas above 78°N, below 60°S, the northern and southern poles, and the Canadian Northern Domestic Area (NDA). The NDA includes the Northern Control Area (NCA), the Arctic Control Area (ACA) and the Area of Magnetic Unreliability (AMU). The NDA, NCA and ACA are depicted on Canadian HI enroute charts and encompass the northernmost Canadian airspace.

Authorization: 14 CFR 135: Operations specification required.

North Atlantic High Level Airspace (NAT HLA)
NAT/MNPS, the North Atlantic Minimum Navigation Performance Specification, has been replaced the NAT HLA, the North Atlantic High Level Airspace.

Where: Most of the North Atlantic and the Canadian Arctic Control Area

Authorization: 14 CFR 91: Letter of authorization required, 14 CFR 135: Operations specification required.

Precision Area Navigation (P-RNAV)
P-RNAV is giving way to RNP-1 and has many similarities: it is used to fly RNAV departure and arrival procedures, requires high-integrity navigation databases, can be flown with GPS, and requires the aircraft stay within 1 nm of course. There are differences which are transparent to most high-tech aircraft.

Where: European Civil Aviation Conference countries (most of Europe) and some other areas throughout the word, i.e., Hong Kong. Terminal procedures will have "P-RNAV Required" annotated.

Authorization: 14 CFR 91: Letter of authorization required, 14 CFR 135: Operations specification required.

Reduced Vertical Separation Minimum (RVSM)
While RVSM is now the standard just about everywhere, there are country-specific rules for flight level selection and contingency procedures.

Where: Just about everywhere in the world.

Authorization: 14 CFR 91: Letter of authorization required, 14 CFR 135: Operations specification required. Note: if you remain within the Continental United States and are equipped with ADS-B Out, you do not need an LOA.

Required Navigation Performance-1 (RNP-1)
Required Navigation Performance-1 (RNP-1) is a new standard for terminal operations but RNAV 1 and RNAV 2 are still in use.

Where: Parts of Australia and Hong Kong.

Authorization: Required only if you will be flying the applicable procedures in Australia or Hong Kong, with several exceptions. 14 CFR 91: Letter of authorization is not required in Australia for foreign aircraft, but is required in Hong Kong. 14 CFR 135: Operations specification required.

Required Navigation Performance-4 (RNP-4)
The Required Navigation Performance-4 (RNP-4) standard is performance based, requiring on-board performance monitoring and alerting. This is as opposed to the older RNAV systems which are an equipment-based standard that do not require on-board performance monitoring and alerting. So, you might say, your airplane and crew are RNP-1 qualified, one is more accurate than four, so you are good to go! Wrong! RNP-4 requires CPDLC while RNP-1 does not.

Where: Parts of Australia, New Zealand, and Japan list RNP-4 as a requirement but allow RNP-10 as a substitute. In theory, ATS can monitor aircraft with RNP-4 more closely and will have traffic priority.

Authorization: 14 CFR 91: Letter of authorization required, 14 CFR 135: Operations specification required.

Required Navigation Performance-10 (RNP-10)
RNP-10 is an exception to the rule that all Required Navigation Performance (RNP) standards are performance based, requiring on-board performance monitoring and alerting. "RNP-10" was adopted by many parts of the world when that really meant "RNAV 10."

Where: The Central East Pacific (CEP) between Hawaii and the west coast of the United States, and portions of the North Pacific (NOPAC) require RNP-10. There are other areas of the world that have adopted RNP-10, such as parts of Africa, the Indian Ocean, Australia, New Zealand, Tahiti, and some parts of South America near Recife. Note: the world is adopting RNP-10 or RNP-4 for oceanic operations, you will need one or the other.

Authorization: 14 CFR 91: Letter of authorization required, 14 CFR 135: Operations specification required.

CREW QUALIFICATION AND TRAINING
Each of the operational approvals shown above have specific training requirements and some countries and airports have their own specific training requirements. You need to check with the country's Aeronautical Information Publication, the Jeppesen Airway Manual, or with your international service handler to be sure. Also consider:

Aircrew ID Cards. (Nothing really mandates this, but these cards will make your life easier in some locations.)

FAA Airman’s Certificates. [ICAO Chicago Convention, Article 29.]

FAA Medical Certificates [AC 91-70B, ¶5.4.1.1]
Keep in mind that ICAO medical classes are slightly different and the valid dates are not like they are in the United States. The expiration isn't at the end of the sixth month following examination for a Class 1 Medical for example. (A medical completed on the 12th day of the month, for example, shall remain valid until the 12th day of the month of expiration.) Further, the 6 month/12 month/24 month expirations cannot be simply tied to the type of license or operation. See: ICAO Annex 1, ¶1.2.5.

FCC Radiotelephone License [AC 91-70B, ¶5.4.1.1]
While this isn't required flying within the United States, ICAO Annex 6, Part I, requires that one member of the flight crew hold a valid radio telephone operator's license. Keep in mind that Part I only constrains commercial operators but SAFA inspectors are instructed to check this for non-commercial operators as well.

Immunization Records
Some countries will require this.

Pilot’s Proof of Qualification 
Some countries will not take you at your word and it pays to have a copy of your most recent training certificates.

Passports [ICAO Chicago Convention, Article 13.]

Proof of Citizenship

PAPERLESS NOTE
There isn't much written about this, but I have asked U.S. FAA and EASA SAFA inspectors and they have agreed that you can go paperless on everything except: aircraft registration, airworthiness certificate, pilot's license and pilot's medical. Everything else can be electronically available. Keep in mind that the more quickly you can produce the document, say on your iPad, the more quickly the inspector is likely to move on.