The environment you describe removes key problems that drove
the development of navigational technology on the Earth,
and introduces new problems (including some that are not obvious)
in their place.
The effect of a horizon
One reason (perhaps the big reason) why it's so often so difficult
to find your way over long distances at sea
is that the Earth itself gets in the way.
If you want to go somewhere more than a few dozen miles off-shore
you need to have a good way to tell that you're going in the right direction
without being able to see either your destination or any other landmark.
With your floating islands, this problem disappears.
Everything is in line of sight
(unless another island is directly in the path, in which case you would want to head to that island first).
Finding your way in the dark
On the Earth, it gets a lot darker at night than during the day,
and things that could have been landmarks are no longer visible.
On the other hand, you can see the stars at night.
Navigators on Earth learned to navigate by whatever kinds of things
they could see, which vary from time to time.
In your cluster, there does not appear to be any reason for things
to be more or less visible at different times.
The Earth's axis of rotation
The fact that the Earth rotates and that we can therefore see the apparent
motion of several prominent objects (notably the Sun!) from east to west
gives some obvious, natural directions for navigation.
OK, you've taken this away, which introduces an obvious problem,
but perhaps relatively minor compared to the next one.
Degrees of freedom of movement
The fact that the Earth's gravity gives us obvious "up" and "down"
directions is secondary to the fact that it keeps practically everything
on the surface of the Earth. Until the development of aircraft
(including balloons) there was no vehicle that could even consider
traveling up or down. All long-distance travel was basically two-dimensional.
In fact, even with modern airliners long-distance travel is nearly
two-dimensional; a flight of 3000 nautical miles will rarely get even
8 nautical miles above sea level.
Even if you had an obvious naturally directed frame of reference in your cluster, early navigators would have to develop ways of directing their craft
that humans have only had to deal with when sending spacecraft to the Moon
or to more distant places.
Although you have line-of-sight to practically anywhere you would want
to go, the space between you and your destination is still filled with
breathable air. The thickness of this layer of air around the Earth
is only a few kilometers--11 km up, density is less than 1/4 of that at
sea level, 20 km up, it's less than 7%, 32 km up it's less than 1%.
So we can still see stars at night.
Wikipedia says visibility through air would be limited to less than 300 km even in perfectly clear conditions--and with entire islands floating around in
mid-air, it seems likely that other particles would be floating about, too.
If the air between islands is really thin, though, that might allow
the radius of visibility to be greater than it would have been in
a uniformly thick atmosphere. And you have magic.
So visibility could be on the order of hundreds of kilometers,
less if you allow any kind of clouding or floating particles.
You could probably arrange to have visible stars in the distance
(maybe only at the distance of the Sun from the Earth--they do have to
be bright enough to be visible through all that air).
But it sounds like that is not a planned part of your world;
it may make more sense for the radius of the cluster to be much
larger than the distance anyone can see from any island,
even with a strong telescope.
The map keeps changing
If even a strong storm can move an island significantly, charts can't be
very precise. If you could somehow plot the exact direction to an island
that was much farther than you can see, it very likely wouldn't be where
you expected it to be when you got there.
Technology matters--a lot
At a very low level of technology I think it is unlikely that navigation
would be advanced much beyond having knowledge of which islands are close
to which other islands.
Since the islands drift, even local "sky charts" would be impractical;
but people on each island would either be able to recognize the
nearby islands or would know which was which by having tracked their
motions across the sky.
Directions a sky captain would give would basically be,
"See that island there? Go to it."
If the island was too far away to see, you probably want to stop at another,
nearer island to get further directions anyway.
Edit: I wrote most of the rest of this answer before I noticed the comment about "no radio ... tech level similar to the 1500s."
That comment makes most of the rest of my originally-written answer obsolete,
but I'm leaving it for reference, underneath the separator line below.
To have reference directions that one can give directions relative to,
the way a captain in the 1500s could give directions relative to the
compass card, would require more effort to keep track of the necessary
reference directions than I think could be supported by the technology.
You'd need either a very stable gyroscopic system or a lot of computing
power to figure out what direction was what based on what you could
see (and on how much what you saw was likely to have moved since it
was last "charted"). So at that level of technology, as far as
directions for navigation go,
I think "go to that island you see there" is it.
Directions to manuever a vessel could still be given by angle of
yaw and angle of pitch (having already
assigned yaw, pitch, and roll axes to the vessel),
but those would be directions relative to whichever way the vessel
happened to be oriented when the directions were given.
Once you have radio technology then the visibility problem becomes a
lot less severe. Radio waves will go further than light through the
inter-island atmosphere, and you could set up radio beacons on each
island that could be identified and located from very long distances away.
The nature of the directions would be similar; the difference would be
that rather than heading to where you can see the island,
you would head in the direction that your radio locator indicated
for the desired beacon.
The fact that the island may drift is of little consequence, since
the beacon will go wherever the island does.
Giving an arbitrary heading to the helm
Eventually, it might be desirable to be able to give some kind of
"heading" direction to the helm of a skyship that doesn't depend on
having a visible island or a beacon in the direction you want to go.
The question is how long it would take for the usefulness of such a thing
to outweigh the technical difficulty of achieving it.
(Keep in mind that the problem of getting from point A to point B without
getting lost at sea, which prompted so much of the development of navigation
on Earth, would already have been solved.)
There are two obvious ways to indicate direction in three-dimensional space.
One is three-component Cartesian vectors; the other is some sort
azimuth-and-elevation system or localized spherical coordinates
using two angle measurements.
Steering by vectors does not seem attractive; do we ever tell someone
to sail "twice as fast to the east as you do to the north"?
So two angles it is. The question is, what are the reference
directions from which to measure the angles?
Any such reference directions would probably be determined by
a universal coordinate system imposed on the entire cluster;
I don't think there's a general solution for specifying direction of
travel without that. The universal coordinate system could
itself be spherical, cylindrical, or Cartesian (or possibly something
else, but I can't think of what).
There is an identifiable center of the cluster in the middle of its "heart".
This gives you an "outward" direction (away from the center) at any
other point in the cluster. This could be one of the reference
directions for the azimuth-elevation directions that skyship captains
would give to their helms; but if so, it pretty much requires that the
universal coordinates also be spherical.
Another possible source of direction could be a magnetic field
throughout the cluster.
The lines of the field don't have to be completely parallel, just pointing
in the same general direction within the space between islands.
A magnetic needle could be mounted so that it always points "north"
parallel to the local lines of the field (unlike a compass used for
navigation on the Earth, which projects the lines of the field onto
the Earth's surface).
Assuming there were known ways to estimate and compensate for the
deviation of the magnetic field wherever the skyship might be,
this would give one axis of a universal system of coordinates that
could either be cylindrical or Cartesian.
The problem with either spherical or cylindrical coordinates, however,
is that directions get ambiguous when you're too near the main axis
of the coordinate system. Which direction is it to New York from the
north pole? Which direction to Beijing? They're both south, which is
no help in figuring out how to fly to one of those destinations.
So I think the universal system would probably be Cartesian.
One axis (aligned with the average magnetic field if there is one,
otherwise aligned with some very important route or with an arbitrary
direction) would be the "north" axis; another would be the "prime" axis.
So that every skyship can always determine the orientation of those axes
despite the drifting of the islands, people might set out a regular grid
of floating radio beacons, with propulsion powerplants
so that they can (almost) hold their stations relative to each other.
Each beacon would report any deviations in its relative position
by a signal carried by its radio transmissions.
By triangulating a few of these stations, you could always determine
where you were and (most importantly for the purpose of this question)
which direction was parallel to each of the axes from wherever you
happened to be.
It is also possible that a skyship would carry a gyroscopic system that
(mostly) stayed aligned with the axes of the universal coordinate system,
which might be more convenient for knowing which direction is which from
moment to moment (especially if you don't have high speed computers to
figure it out for you),
but I think the regular grid of fixed beacons would still be useful
to help correct any wobbling of the gyroscopes and to reset them if
they tumbled completely.
Then to specify direction, think of an imaginary Earth's surface positioned
with your skyship at the center of the globe, with the north pole
exactly "north" from the skyship and the point at zero latitude and longitude
exactly in the "prime" direction from the skyship.
A command to head 30 degrees north, 50 degrees east would mean
to point the skyship toward the point at latitude 30 N, longitude 50 E
on that imaginary globe.
(But I think it is likely that the "latitude" direction might be given
as an angle away from the north direction rather than toward it;
that is, you might say "head toward zero south" if you wanted to
head exactly in the direction of the "north" axis.)