I'll just lay out some of the options; which one works best for you is something for you to decide.
In terms of airports, Catania is Sicily's biggest, followed by Palermo. Trapani is significantly smaller than these two, and Comiso is much smaller again. To see which airlines fly where from each airport, look at that airport's Wikipedia page.
From the Italian mainland, Rome has by far the biggest selection of flights to Sicilian airports, followed (roughly equally) by Milan and Naples. Other cities usually have 1-2 flights a day to Catania and Palermo.
To find all flights you can use Skyscanner: http://www.skyscanner.com/. You have to then check final prices with all the charges at each airline's website. Note that for domestic Alitalia flights, Alitalia's International website has the same prices as their Italian one, but has an English option. The Alitalia US website shows higher prices for these flights. Since Alitalia includes one checked bag and has a more generous carryon allowance than some budget carriers, it can work out cheaper in the end.
For getting to Sicily from the US, there are nonstop flights from JFK to Palermo a few days a week, a few months of the year (I don't think they run in May). Otherwise you have to change in Europe. It's best if you get it all on one ticket, so you're "protected" if you miss the connection due to a late arrival. Just make sure your connection does not involve changing airports. For instance, Air France flights from the US land at Paris CDG, but their flights to Sicily only leave from Paris Orly.
If you do have to be on separate tickets (I did, as my miles would only get me from Philadelphia to Rome), then consider buying two tickets. I bought one from Rome to Palermo three hours after my scheduled arrival, and one ten hours after. I knew I'd use one and throw away one, and counted the cost of both together as the cost of the flight (it was still cheaper than a last minute ticket for my travel day).
There is an overnight ferry from Naples to Palermo. Trains from the mainland to Sicily go on a boat for the short trip across the Straight of Messina.
Train service in Italy south of Catania (Calabria, Basilicata) is sparse. If you want to explore this region, you'll probably want a car. You may find it easier to just keep your Sicily rental and take it to the mainland (since you'll probably want the car in Tuscany as well), dropping it at Piazzale Roma in Venice. Of course, you'll need enough time to make this "whole of the boot from south to north" worthwhile. Even doing it at a rapid pace, what you want to do in Sicily alone will take 7-10 days.
If you want more Sicily ideas and some of my experiences with the logistics of car rental, driving, and the like, my VERY detailed trip report from April-May 2014 is here: https://community.ricksteves.com/travel-forum/trip-reports/sicily-palermo-caltanisetta-siracusa-taormina
