There are many ways to find sky islands:
###Pre-Hardmode
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.
###Hardmode
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.
###Other
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.