Budget airline Virgin Blue will begin flying to Christmas Island three times a week from April .
Virgin Blue flies to Christmas island