Hi, Ish. What software do you wish to use to add the text, borders, etc.? This will help us help.
As for fonts, my suggestion is "Fire of Yzgard" at http://www.dafont.com/theme.php?cat=402&page=4 ; I say this because your map is too modern/realistic-leaning to support truly medieval or hand drawn fonts; Yzgard is a nice compromise--although click through those Gothic>Modern fonts at Dafont; there are hundreds of possibilities.
When you place text in, I'd say perhaps go reddish with a light, white shadow. This will allow them to stand out. But color coordination is my weakness, so I'd just play with it.
I would not put this map on parchment (again, it's too photorealistic), but give it either an ornate frame of a repeated pattern or a simple series of black lines. It may be a nice effect to have the color of that frame to play off the same blue of the ocean's blue (or a close neighbor).
I hope this helps get you started with some ideas! Keep us posted!