This is a good question, one that leads to many roleplaying hooks. Why? Because it's not as easy as it sounds. Sure thing you can let them "smell" each other, but that would be a bit to easy and wouldn't take all the orphaned changer into account.
There are some Gifts that help with recognizing fellow Garou, some of them even for beginning characters. Same thing for the hints everybody drops from time to time.
But there is an even better way to get your PCs to know each other: Elder. The Garou are few and between so it's easy that they are known since the First Change. Stargazer are to few to go unnoticed (and Chimera keeps an eye on his Children like Raven does with his Corax ;) ), and Silver Fangs keep records on everyone in their lineage to lose someone.
Every Adren, Athro or Elder knows enough to recognize signs to at least suspect a First Change in his vincinity. Thanks to Moon Bridges it is easy to travel (even in the Dark Ages it was a breeze for Changer).
So, there are many ways aside from "just" rolling Perception (not that it isn't a viable option, don't get me wrong). If you want to keep adding to the mysticism that is part of Werewolf, take the way with the spirits or Gifts. If you want to focus a bit more on the political part, introduce Athros or Elder that seem to know everything. Or let them wander around a bit, till they find out about it in the heat of battle ;)