Cheap ESD/safety Mat
Broadly, there are two different types of commonly used ESD bench mats:


2-layer nitrile rubber.  These will not melt if solder drips on them, or even if you place a hot iron directly on them.  Physically, they are very resistant to cuts and scratches.  They have almost no give.
3-layer vinyl.  These usually have a little give to them so are nice for mechanical assembly or packing workstations.  Molten solder will damage them however, and they're not as physically tough.


ESD floor mats can be a little more diverse, you can usually get anti-fatigue, etc. depending on your budget.

Here's a nice video to compare the two:

http://www.youtube.com/watch?v=9c7kTF4cF6w