I went with some friends in 2004, in April.
From Hervey Bay we took a day trip across to Lady Elliot Island. They offer everything as a day trip, or you can stay on the island for longer if you wish.
This included a flight in a small plane for the 40 minutes to the island, walking in reef shoes around the island and seeing the coral and shallow-water fish.
Then you could go snorkelling and swimming for a few hours or just explore.
A meal was included, and then in the afternoon we went on a glass-bottomed boat around the island as well, allowing a relaxing view of the many, many fish, and even some huge turtles!
Finally you fly back in the late afternoon.
It's a great day trip, I felt it was enough to 'tick it off', but some may wish to stay longer - especially if it's your thing. We only had a short trip to Aus (from New Zealand), but certainly if I was travelling from afar and backpacking (the sort of travel I prefer now) I may have spent a night or two relaxing on the island - certainly when I went to Tonga, that sort of experience was fantastic.