I have been doing a great deal of research in this area myself. It is very complex. Do not hesitate to use a service such as Universal Weather and Aviation to get you started; it will probably save you a ton of time and you will be able to take over most, if not all, of the work yourself after a few trips.
Some things to be aware of are the requirement for a U.S. customs bond and using APIS for 135 operations. Be very careful when bringing passengers back to the U.S.--everyone requires a passport after the first of the year, and if someone is other than a U.S. or Canadian citizen, or a permanent resident alien, a Visa is required when arriving by "private" aircraft (yes, even for someone from the UK, Germany, etc.). This includes 135 ops for this definition. Violations lead to a fine and the passenger's deportation--at your expense.
All three countries you mentioned require you to have prior permission of some kind to conduct a charter.
Canada requires something called a "foreign air operator certificate" for U.S. charter operators; go to the Transport Canada website for a description of the process to obtain one.
The Bahamas requires a permit for any commercial flight; they can be issued on an ad-hoc basis or annually. They have a reasonable turn time on the ad-hoc permits, but don't try to do it with less than a week lead time. The annual permit application is quite involved, but if you go there often it might be worth the time. Anthony Dean is the civil aviation representative who handles these permits and is very helpful.
Mexico is something I have no direct experience with other than with 121 ops. I know Mexican insurance through a Mexican company is one requirement. Our plan is to use Universal to get us set up for the first several trips, then maybe start doing some of it ourselves if necessary. You can choose the services you need ala carte, and honestly the cost is not that great relative to the expense of a jet charter so my intention is to simply pass the cost on to the customer. It's really not worth screwing around with this stuff to save a couple of bucks because one little thing can totally wreck a trip, and that's not good customer service. I think they'd rather pay a little extra and have a smooth experience. The people at Universal do this all day long, so they know what is required.
The "entry requirements" and "air traffic control" tabs in the Jepp coverage for each region give detailed info about permits, operational differences, etc. if you want to research them yourself.
Also, remember that international ops are not as flexible as domestic ops, so take your time and be extra careful if there are any itinerary changes.
Good luck,
Josh M.
