So for the the coastline, you mean something like in these maps: Click image for larger version. 

Name:	map-ink2.png 
Views:	417 
Size:	1.13 MB 
ID:	58545Click image for larger version. 

Name:	map.jpeg 
Views:	339 
Size:	997.6 KB 
ID:	58546

You can sort of pull it off in raster software like GIMP, but you tend to get artifacts of the raster grid creeping in. Vector software like Inkscape or a proper GIS will generally give you better results. The Outset lines int he canada Map were done with QuantumGIS using the "Buffer" operation, while those in Baakoi were done in Inkscape with the "Outset" operation.

And by "Rosette Chart" I think you mean a Portolan? Click image for larger version. 

Name:	aug-sept-outline.jpeg 
Views:	156 
Size:	864.6 KB 
ID:	58547 A Portolan is a map designed for "Dead Reckoning" a form of marine navigation used in the 15th century. It amounts to "take a compass bearing, and keep following the compass until you hit land, and maybe try to figure out how fast you are going to get an idea of where you are along that line." It's not very accurate (As it's very hard to figure out your speed and doesn't account for sideways drift) or very efficient over long distances (as it doesn't follow great circle paths) but it's a big improvement over just hugging the coast.

Being a programmer is a big help actually. All three of the maps I included involved some programming on my part. The web of rhumb lines on the portolan was done in Ruby. The names on Baakoi and the Portolan were all generated with a name generator, again in Ruby, and the tree placement on the Canada map was done using a centroidal Voronoi stipple generator I wrote in Java using JTS.