Conquistadores and explorers are real easy to miss, especially if you're involved in a war at the time they show up. Here are a few helpful tips, beyond those already given:
Listen for the trumpet TA-DA! When you hear that, you know something important has happened, and it could well be notification that you've got an explorer/conquistadore. Check the message scroll at the bottom, and it will tell you if one has showed up. Listen also for the "Ooohhhh!" sound that indicates someone has died, and then check the message scroll -- this will notify you of the death of leaders, including explorers and conquistadores -- something which is important to keep track of. Invariably they die in the middle of an expedition, or right when you are preparing to use them for something big . . . .
Use your archive "leaders" page (the archive is the book at the right side of the bottom left window on the main screen. It should be somewhere between pages 23 and 29 -- can't remember exactly.) Regular admirals have an anchor sign; explorers have a sextant; regular generals have a pistol; conquistadores a helmet icon. The leader screen will tell you the name of the army/fleet that the leader is currently commanding. It would have been a lot more helpful if it told you the province they were in, but maybe that's something for a later patch/edition.
You can periodically review your fleets and leaders by clicking on them; the "status" box that pops up on the left will have the symbols by the name. Note also that the unit icons on the screen will have a tiny sextant by the fleet or helmet by the figure to indicate whether they are conquistadores or explorers. If they are currently in a fleet or army and subordinate to the main leader, the little square picture with their name will appear in the lower part of the status window to indicate they are present in the force but not commanding. You can then reorganize the force/fleet to separate them.
A good way to spot an explorer or conquistadore is just to scan the map for any fleets that have popped up at ports, or 1-3 strength ground units that weren't there before. Sometimes they pop up in a larger force, sometimes they pop up by themselves.
There's a lot to keep track of in EU, but after awhile you'll be able to find those pesky folks fairly easily.