Late in the medieval age, overseas combat is a bit harder (depending upon how far away your enemy is). It gets much easier in late industrial age, with transports and airlifts.
Plan to use overwhelming force, since you can't bring in reinforcements as easily. Your enemy can reinforce a battered city faster than you can bring a second wave to finish it off, so you want to bring enough forces so that there is no doubt you can take that first city in one turn, and hold it against a counterstrike.
Don't forget to bring some workers over in that first wave, so they can immediately improve that first city. Even if you don't want that overseas city to be a productive city, you do want some population there (for the defensive bonuses of having a city and eventually metropolis), and roads make your subsequent attacks out from your newly captured city all the more quicker.
One strategy is to plan your attack in two steps, dividing your forces. The first force is a small force of defensive units to make a diversion, the second force is your invading force. Strike with the diversionary force first, your ideal target being a mountain or hill on your enemy's coast, away from your planned main staging area. Hopefully your enemy takes the bait, masses its forces against your diversionary unit, and takes heavy losses. The very next turn, land your main invasion force. Even if your enemy destroyed your diversionary unit, they are out of position and can't get back to your invasion force before you can attack your first city.
You will need plenty of ships. The rate at which you can reinforce is limited by the ships you have available. You need them not only as transports, but to defend against enemy ships who will come and harass your new city.