Gelpro Mats - do they work?
I find a pair of basic Crocs to be very efficient as kitchen clogs. (As does Mr. Batali, though the orange color may be in questionable taste). They are well cushioned, reasonably priced, and easily cleaned. They won't provide a ton of protection against dropping something heavy, sharp or hot, though they do sell some upscale models that provide more.

If you really want a mat, these Wellness Mats are superbly cushioned.