Before talking about the story of Julius Caesar and the pirates, there are two important things to remember about it: 1. The sources that have all the fun details like how he was angry that the pirates set his ransom so low, or how he told the pirates every day that he would return to crucify then, which they took as a joke until he did it, come from sources that were written well after Caesar's death and deification. The two most commonly used accounts are from Suetonius and Plutarch, both of whom wrote after 100 CE, thus a full century and a half after the deification. Velius Paterculus, the other important source, wrote much earlier (around the late 20s CE) and did not include fanciful details like him practicing public speaking or participating in the pirates' athletic competition. Paterculus was also something of a court historian for Tiberius, which is important given point two: 2) Julius Caesar's great rival Pompey won great renown for his grand military campaign to clear the Mediterranean of pirates. It doesn't take an overly cynical perspective to see how convenient it is that, actually, Julius Caesar had his own cool story about pirates! This isn't to say we should treat it as fabrication, for all my caveats it is relatively well attested, just that it also needs to be treated very carefully and, from a personal standpoint, it is somewhat hard to know what to make of it. Personally I think the best way of the story is in the manner of Maria Wyke's excellent Julius Caesar: A Life in Western Culture which is something if a meta biography, tracing different events in Caesar's life through the ages and showing how they morphed and changed to fit a particular view on this most discussable historical figure.

As for how Caesar could have found them, the answer is actually pretty straightforward: classical pirates were not Jack Sparrow like nomads of the Mediterranean, constantly traveling from port to port, but rather a sort of communal navy that engaged in more or less the same tactics as the "states" of the ancient world but were not afforded legitimacy by whoever wrote down the few things that lasted until the present time (One can compare the rhetorical use of the term "pirate" to the modern use of the term "terrorist"). The upshot being that Caesar did not need to follow a trail of breadcrumbs from port to port looking for a particular ship and crew, he just needed to go back to where he was held and crucify everyone. And indeed, the ancient sources do not make any not of his being able to find the pirates, merely his being able to raise a private military force quickly in spite of the governor's reluctance and return to the location where his ransom had been sent and fall on the pirate fleet. Paterculus even says that the pirates sent hostages to the cities of Asia along with the ransom demands, further underlining how these were not sneaky criminals squirreled away in a hideout. It was all quite open and formalised, the pity for the pirates being that they happened to kidnap a Roman nobile who had spent time in Bithynia and thus had a number of connections with the region allowing his to circumvent the official adminstrative authority which was reluctant to use military force in that matter.

For the difficulties of the story, the Wycke book mentioned above as well as Josiah Osgood's paper "Caesar and the Pirates" (useful here because you can find it through Google). For ancient piracy, Philip De Souza Piracy in the Graeco-Roman World is still essential.

I'm reproducing the Paterculus in full here, taken from LacusCurtius (there is also a roughly contemporary account from Valerius Maximus as well but it is basically the same thing but without a readily available English translation):

Later, but when still quite a young man, he was captured by pirates and so conducted himself during the entire period of his detention as to inspire in them to an equal degree both fear and respect. Neither by day nor by night did he remove his shoes or loosen his girdle — for why should a detail of the greatest significance be omitted merely because it cannot be adorned in imposing language? — lest the slightest change in his usual garb might cause him to be suspected by his captors, who guarded him only with their eyes.

It would take too long to tell of his many bold plans for the punishment of the pirates, or how obstinately the timid governor of Asia refused to second them. The following story, however, may be told as a presage of his future greatness. On the night following the day on which his ransom was paid by the cities of Asia — he had, however, compelled the pirates before payment to give hostages to these cities — although he was but a private citizen without authority, and his fleet had been collected on the spur of the moment, he directed his course to the rendezvous of the pirates, put to flight part of their fleet, sank part, and captured several ships and many men. Well satisfied with the success of his night expedition he returned to his friends and, after handing his prisoners into custody, went straight to Bithynia to Juncus, the proconsul — for the same man was governor of Bithynia as well as of Asia — and demanded his sanction for the execution of his captives. When Juncus, whose former inactivity had now given way to jealousy, refused, and said that he would sell the captives as slaves, Caesar returned to the coast with incredible speed and crucified all his prisoners before anyone had had time to receive a dispatch from the consul in regard to the matter.