I've been playing Terraria for a while, and I'd like to get up onto those Floating Islands for their loot (mainly interested in the Shiny Red Balloon).
What is the most reliable and/or easiest method to locate these Floating Islands?
One of the best and quickest methods (apart from external map viewers) is to use Meteor Shot or Water Bolt. Just keep walking on the ground and shooting bolts straight up, if they bounce back there is an island above you.
More information and other good tips can be found here.
I've found that using several gravitation potions is the most efficient method to locate floating islands.
Really the only downside to them is that they are rather difficult to obtain early game, as you can only find them in pots and chests until you are able to obtain fireblossom and feathers.
There are many ways to find sky islands:
The "traditional" method (the way most players have done it since the earliest versions of the game) is to use meteor bullets or water bolt to shoot a projectile upwards, then wait to see if it comes back down. If it does, there's a sky island above you.
If you have a stack of dirt/sand, you can build a pillar straight up to see if you run into an island. This is very tedious, since you'll usually want to tear down the pillar after going up, and depending on the speed of your pickaxe this can be aggravatingly slow. It's also dangerous in the early game, especially if you don't have a grappling hook or cobalt shield to anchor yourself to the pillar, since Harpies will knock you off and make you to fall to your death. The rewards can be very worth it in the early game though. Rope also works for this trick, and it makes ascending/descending a little safer.
Gravitation potions drop infrequently from pots and can also be found in chests underground or from fishing. Using one can let your explore the sky freely, but be careful - you can still take falling damage even when falling upside down.
The Queen Bee has a small chance to drop the Bee mount, which grants limited flying ability. Though its horizontal distance is pretty lackluster, you can easily fly vertically to find any sky islands in your world.
The Wizard, once found and freed, sells the Ice Rod, which can create temporary blocks of ice in midair. Combined with a grappling hook, this make aerial travel quite simple.
Once you get your first set of wings, getting to the sky islands is pretty trivial, especially with late game wings. Of course, actually obtaining the wings without access to Souls of Flight from Wyverns can be a bit of a problem... you'd have to get lucky and get a pair of Fin Wings from the Angler quests or a set of dev wings from a boss bag in Expert Mode, or you'd have to buy a set from either the Steampunker or Witch Doctor.
In earlier versions of Terraria (prior to v1.2), sky islands had various rare ore deposits scattered around. Occasionally, due to a world generation bug, these ores could spawn on the surface in addition to on the sky island. If you ran along the surface and found silver or gold, there was a strong chance that a sky island was directly above you.
An efficient way to find them is constantly flying with wings/a flying mount(e.g.Cosmic Car Key/Bee Mount). Up from 1 to 3 floating islands can be found in small worlds and from 1 to 8 in large worlds. After a few in-game days, most part of the map will be covered in this way, and if you have luck, you may found a lot of floating islands. The Water Bolt is the harder way, since you must wait until the bolt comes back and it's also found pretty hard.
The easiest way to get wings is going in the hardmode underground jungle biome, make a house there, and wait for the witch doctor to come in. It must be night when you go to the witch doctor to get the wings, and you must have 1 platinum coin at you too. Once you get them, you'll easily be able to get to floating islands, but beware of Harpies and Wyverns.
The flying mount is completely optional, but just so you don't have to get down after some time.
Hope i helped you with this tips.
If you wait until hard mode Wings might be useful. That's what I did to find Islands