Since stars have been used in navigation for so many years, I think it would be fitting to have constellations with treasure underneath. Additionally, the night sky being so beautiful, I want more excuses to look at it.
Similar to the ship/skull clouds, there would be a constellation; leo, cancer, Mr. Pants, etc. floating over a random island. Underneath would be a treasure for that constellation: A treasure chest marked with the constellation on the lid, a skeleton glowing with the constellation on its forehead whom you can battle, or a mystical crate adorned with the constellation.
Alternatively, there could maps that tie in with the night sky, where, instead of saying to visit a particular island, it simply shows the constellation to go towards and under.
