The rules for service of process are generally included in a state's stautory Code. A summary of each state's rules can be found the state's legal encyclopedia or a treatise on civil procedure.
Companies: U.S. companies are generally required to file with the Secretary of State in each state where they do business. This filing usually includes a registered agent designated to receive service and an address where the agent can be served. For information on how to get a record of the Secretary of State filing with this information, see "Secretary of State Records."
Banks in N.Y.: In NY, all out-of-state banks must designate the Superintendent of Banks to receive process for them (NY Banking Law, Section 200), even if they are in liquidation (Section 206). See also Section 34 and cross sections listed there.
Unions: Unions are generally not incorporated and do not file business registration records with a Secretary of State. State law determines how to serve process on a union (e.g., under Virginia Code § 40.1-68 you serve the "clerk of the State Corporation Commission"; under Florida Code 48.141 you serve the "president or other officer business agent, manager or person in charge").
The main treaty on serving process abroad is part of The Hague Convention, "Service Abroad of Judicial and Extrajudicial Documents in Civil or Commercial Matters" [TIAS 6638], which is reprinted in the United States Code (see "Hague Convention"); it is also posted online by the Hague Conference on Private International Law. For more information, see:
(1) The U.S. State Department's Service of Legal Documents Abroad page.
(2) The Practical Handbook on the Operation of the Hague Convention of 15 November 1965 on the Service Abroad of Judicial and Extrajudicial Documents in Civil or Commercial Matters (HCCH Publications);
(3) "Service of Process Abroad: A Practical Guide to Service Under the Hague Service Convention and the Federal Rules of Civil Procedure," 24 International Lawyer 55 (1990);
(4) One of the other publications listed in the guide to Service of Process Abroad posted by the Westminster Law Library at the University of Denver.
For information on individual countries, check out (1) the Martindale-Hubbell International Law Digest summaries, usually under "Actions" or "Process" and (2) the State Department's excellent Judicial Assistance page. For more information, call the State Department's Office of Overseas Citizens Services (202-647-5226), which compiles legal sheets on many countries.
If that doesn't work, call the country's U.S. Embassy (usually in D.C.), the country's Mission to the U.N. (usually in N.Y.), the U.S. Embassy (in that country) and/or an attorney practicing in that country.
Note on Agents: In many countries, domestic corporations do not designate agents to receive service of process. They just provide an official address where service can be made. I have been told that this the case in Canada, China, Japan, South Korea and the United Kingdom. To be sure, contact the relevant country's business registration agency and/or the International Services division of CT Corp (800-428-4685).