In terms of flat maps as we know them, the mapping could be in fact be rather similar to maps in our world. We have longitude and latitude grid lines on maps, and a similar method of charting positions could be explored, using two lines emerging from every mapped island, air and magick. The maps would be circular, with the islands arranged around a center (which could possibly have the same air and magick lines as the other islands, if the map is centered on an island).
Magick lines go through the center of the map and through the center of each of the islands at their current position, air lines map to the wind eddies and patterns around the island, and the island travels along them just as it does the magick lines. The mapping of wind lines would probably be done with some sort of balloon system, otherwise knowledge of the weather, probably through magic, would have to be obtained. Along every air or magick line would have to be placed some sort of formula to be able to calculate, from the difference in date of creation of the map to the present, how far along the lines the island would have moved, and in which direction, it's highly likely that some sort of special calculus or shorthand would evolve over the years to write this. It goes without saying all maps would be dated.
When it comes to air lines, what might be important to consider is that as an island moves across some air lines, it may encounter separate air lines and be whisked away in those wind currents, in which case, wind lines wouldn't be restricted locally to islands, but rather all global wind currents would be drawn on the map, together with their strength, and all islands would be labelled with some form of weight metric, with a formula to decide whether it will be affected by a certain current.
Globes could be very interesting structures, made of spheres and poles. A number of poles would originate from a central sphere, representing magick lines, and on each pole would be a sphere, an island, from which would spring another pole representing air lines. There would be some sort of dial which would enable you to enter the date and the globe would mechanically move all the spheres to the correct place, or possibly, the globe would move automatically every day.
As SRM mentioned, it is highly likely that a more permanent form of navigation would be implemented, using lights and angles, similarly to old nautical navigation. One such implementation might be a sort of sundial placed on an island, however, the "sun" is not in fact the sun, rather, some arcane light emitter placed on a nearby island, set up so that its rays will fall on the sundial on another island, and the precise angle and distance of those two islands can be measured. Of course, as tech level improves, this method will improve, but this is a low tech level example.
Some form of 4D (or even 5D) coordinate system would develop, 3 spacial dimensions and an extra value, correlating to our form of calculus which defines how much an island moves by wind or magick. As SRM has stated, a role of "harbourmaster" or cartographer would become incredibly important, as they know the ins and outs of how each island moves. It is quite likely that these "elders" would be the silent power of your world, and should they organise, could become a formidable political body.