All randomly generated worlds feature at least one island floating in the sky, but they're difficult to access normally and you still need to find where exactly the islands are!
One way to find the islands is to construct pillars that reach far into the sky (100 to 200 blocks in height), then use vines and grapples to scale the pillar (or simply make really tall ladders) and jump in various directions from the very top. With luck you should catch the telltale signs of the floating islands in the form of the vines that often extend below them.
Or load up a gun with Meteor Shots and begin shooting at the sky at random locations; if the shot rebounds back toward you, you've likely hit a floating island. Crafting Grav Potions are also another way to help you navigate maps in special ways.
If you don't mind gaming the system, you can also create a new and separate game in Hardcore mode, purposely kill yourself to become a ghost, then fly around the entire map to eventually discover the islands. Then reload your usual save file and make your way to the islands with the knowledge you've just earned.