What is the best way of converting a gif of a map into a vector format, such as a shapefile?

The only relevant parts that I am interested in are the outline of the island so I realize some manual work will be necessary where it is shaded orange; is there a way to handle the rest?
Regarding copyright, it's from the 1980s and it's being used for academic research.

And figuratively, you can save them as KML or KMZ (compressed KML) files.
Click this link: http://www.iapad.org/p3dm_process/step_04b.htm
– zearth Aug 26 '11 at 02:22Maybe can ease your work. Good luck!
– zearth Oct 06 '11 at 04:46