Getting there

There is a ferry that leaves from Gladstone Marina (Curtis Island Ferry Service) twice a day on Mondays, Wednesdays, Fridays, Saturdays and Sundays. The ferry takes just under an hour, and cost us $60 return for two people.  The ferry drops you at the South End boat ramp.  From here, walk along the road into town - this takes less than 10 minutes.  The road follows the coastline to the left before veering off to the right to reach the eastern side of the island.  There is a general store on the eastern side if you need more supplies.  From there, take the concrete stairs down to the beach for the start of the walk.

Maps

We were unable to find a decent topographic map, Dept of National Parks have this one, which gives a rough idea: http://nprsr.qld.gov.au/parks/curtis-island/pdf/curtis-map.pdf

Route/Trail notes

The first section of the walk is along the beach, this lasts for about 3 or 4km.  When you reach the headland, there is a 4WD drive track and a sign saying "No Camping".  To the right of this sign, there is an unmarked rocky track, between two pandanus palms.  This track looks like it could have once been a 4WD track.  Walk up the track to the top of the headland.  When you get to the top, you will see some great views, as well as the 4WD track.  Follow the track north, around the gate that says "Private Property" (nobody seems to pay any attention to this).  This track leads along the headland for about 12km, and through another gate.  Eventually, you will come to a fork in the road.  There is a sign (the first sign you'll see on the walk) pointing left to get to Turtle St and Joey Lees.  However, the road that leads off to the right also goes to Turtle St beach and is a much nicer route.  The road to the left goes through marshes and is well shaded.  The road to the right continues to follow the headland around, and has much nicer scenery.  This road forks again, and you can walk straight ahead to a nice lookout, and then come back and follow the road down a hill until you come to Turtle Street beach.  We arrived and left at low tide, however I imagine at high tide you may need to take off your boots to walk across a shallow stream that leads out to the ocean.  The official camp ground is across the stream and about 200m down the beach.  Bring insect repellant as the mozzies and midgies are out in full force here.  The beach is really beautiful, and the sunset is spectacular to watch from here.  Apparently there are caves that you can explore at the northern end of the beach at low tide, however we only found out about these after we got back.

From here, I've been told that you can follow the 4WD track that leaves from the northern end of the beach and after about 14km will get you to Joey Lees campground.  From Joey Lees, you can walk along the beach to the northern end (Cape Capricorn) and Yellow Patch campground.  It'd probably take at least 3 days to get there.

Permits/Costs

Barge: $60 return for two people
Camping permit: from Dept National Parks - about $10

Other References

We found it very difficult to find any info at all about this walk.  The South End general store owner (Ailsa) has walked to Turtle St and knows the local area very well.