Type M or S. You can specify adding air entrainment to the mortar which will increase freeze/thaw resistance, but I never do and have had no reported problems. (My practice is in the Northeast US). Some premixed masonry cements already have an air entrainment compound in them by the way.
Adding air entrainment can make the mortar less likely to freeze during cold weather while it is still green, which is something to keep in your pocket if you need it. But on balance if too much air entrnmnt is added it will weaken the mortar (doesn't bond as well to the units). Ae isn't something that can be controlled easily so I prefer not to use it.
