Sometime towards the end of the campain (turn 180 ish?) Sorry don't know exactly when, you will notice that the minimap in the bottom left of the campain gets an extra 20% of black nothingness added to it. I'm fairly sure there's a message at this time to hint that it's there. When that black area appears you just need to send a boat directly west from Lisbon or directly west from Ireland and you'll find it, eventually.