If someone in the 14-15th century world had the knowledge required to build an engine for use in locomotives and ships, what kind of engine could be made using technology that already existed back then?
But the first recorded steam engine was as early as the 1st century Egypt so the principles were known 1500–1600 years before your time-frame which means it's far from a great stretch for you to say development of steam engines that entered common usage was a little earlier in your world.
The propeller didn't come along for a while longer than that of course but paddle steamers are simply a reverse water wheel (which the Romans had) and Archimedes' screw also existed then, so that gives you two potential methods of transferring power from the engine to propel your ships.
Paddle steamers are your most likely ships, especially as the Romans already had ox powered paddle boats (there's a reference to them in the link).
Though this horizontal design is a touch more elegant to my eye.
They'd probably be wood burning rather than coal.