I live in Pittsburgh PA so dealing with floor mats that are covered in salt is nothing new. My plan of attack for these items is take a Shop Vac with a stiff brush attached to the end and vacuum as much of the salt off of the mats as possible. Its been my experience that it is much easier to get the chunks/layered salt off of the mat while they are 100% dry. If your brush is stiff enough and your shop vac strong enough you should be able to get just about all of it off of the mat. Now what remains I remove using the hand tool portion of my Bissell DeepClean Liftoff carpet cleaner. As far as cleaning solution goes I like to use a product called Natures Miracle Deep Cleaning Carpet Shampoo, this is an enzyme based cleaner (uses living bacteria). I found that not only does it work really well on removing just about any kind of smell you can think of it also works well on floor mats covered in salt... You can find this product at most major stores, but if you have issues locating it go to some of the major pet stores. The only downside to this product is the cost it is a little on the expensive side for carpet cleaner.
Off topic, but if you encounter a customer with an odor issue I would recommend using this product for that as well. They also have another cleaning solution that is not for use in carpet cleaners, but works a lot better for removing odors and makes for a good pre- treater that is worth checking out. Both of these products leave little to no odor after use.