Firstly, welcome to the Guild!
By 'more medievalesque' I'm guessing you mean a more aged antique look? If so, one easy way to do it is to create or find a free parchment texture and set it up on its own layer on top of everything else. If you set that layer to 'Multiply' or 'Overlay' it will have the effect of merging the pattern right onto your map. It's worth trying some of the other Layer Settings too, to see what kind of interesting effects you get.
Try combining more than one pattern, too; use those layer settings to create fusions of multiple layers. As with much else in photoshop, just playing around and experimenting is oftentimes the best way to learn how to get cool effects with this.
You can also get different, distinct patterns to show only on certain features (like on the land only, the ocean only, etc) by selecting only the relevant bits and applying the pattern/texture only to them.
If you'll take a little bit of critique about your map itself, you have some serious river issues - see
this thread for pointers.