berjaya air is the only airline flying straight into redang island
http://en.wikipedia.org/wiki/Redang_Airport
alternatively you can travel to kuala terengganu using firefly airline, then a 75-mins ferry ride to redang island
http://wikitravel.org/en/Kuala_Terengganu
both airlines use propeller aircrafts. i personally have not used any of the 2, but i've friends who had n they gave good feedbacks
may be worthwhile for u to check out holiday packages at berjaya-air website, its all inclusive (airfares+full board+transfer+snorkeling trips)