• We have updated our Community Code of Conduct. Please read through the new rules for the forum that are an integral part of Paradox Interactive’s User Agreement.
Did you try the faq's?

You can't buy explorers or conquistadors, you can get either historic or random event ones.

With low marine tech, fleets suffer attrition when at sea for a prolongued period. Send them back to harbour once in a while, if you want them (and your precious explorer) to last.
 
First, you get a message saying that you have gained a new leader. Then- explorer is with the navy- he has sextant (you know, that naval equipment used to measure coordinates) sign next to him, conquistador has one of those old-fashioned helmets. You can also look it up at the ledger- under military
 
Well I do not know., what you do, but getting columbus only halfway across is quite a feat.

He has a rating of 6 for navigation (the first one) and so can stay 12 month out in the sea without suffering any attrition. adding a few more before three ships are gone through attrition, that gives you 18 month. thats enough to sail straight west until you find the carribean, explore to sea zones there and return with one or two ships. Of course you need to start from Gran Canaria and do not stray from the path to much.
Finding a land area in the first try is a question of luck (I would say about 50% if you explore 3 sea zones), but if it fails you just come back next year. And remember to have a few ships ready for him, to take care of the attrition losses.

Ciao
Kulko