> why did I never even question if Apple Pay/Google Pay would work when they originally appeared in Canada?
Because you expect things to work.
> As in you need a special Apple Pay compatible POS?
POS terminal should support RFID [0] contactless payment to be able to talk with a card or phone, but the main thing is "Payment Tokenisation Specification"[1] and it should be supported by the bank of the merchant both in processing and legal agreements.
iOS device doesn't store your credit card (and it can't, otherwise it would be trivial to copy cards), but a token which is tied to your card.
Overall it's very interesting to look at [2]
[0] https://en.wikipedia.org/wiki/ISO/IEC_14443
[1] https://en.wikipedia.org/wiki/Apple_Pay#Technology
[2] https://en.wikipedia.org/wiki/Apple_Pay#Availability