How do they know it's the first day of issue for that stamp? Do they automatically check all mail for first day stamps?
"First-Day" cancellations are generally available only at the Post Office (or designated supporting site) that is the location of a stamp's first day of release - they are not available at post offices across the country. Also, "first-day" cancellations are generally created to order vs. being placed on every piece of mail handled on the corresponding day. In general, regular mail will be given the standard cancellation. Though the standard cancellation will feature the First-Day date, it will not include the "First Day" special cancellation mark. (I say "In general" because there is always the possibility of exceptions!)
So, for example, the 1960 commemorative stamp that was issued for the centennial of the Pony Express was issued at Sacramento, California. Those desiring an official First-Day cancellation of the stamp needed to send an order to the Postmaster in Sacramento; the order needed to include a self-addressed envelope. Over time, private services were started that worked with the Post Office (and now USPS) to have volumes of unaddressed envelopes First-Day cancelled for collectors; such pieces never enter the mail stream.
Today, the USPS makes pre-packaged, un-addressed FDCs available on its web site and in many locations across the country. As with the above, these unaddressed covers never enter the mail stream.
Hope that helps!