Based on the original description of the stamping, you are actually looking to DEBOSS, which is impressing into the mat instead of EMBOSS which sticks up through the surface.
The bad news is that it takes an extremely strong press to be able to deboss a 4 ply mat and many shops don't want to take on this type of job, or charge a lot of money because it is very slow and the thickness of board requires quite a bit of press adjustment. However, if you have access to an etching press, it can possibly be done. (Check with your local college art department) The consistency of drive depth is important to the success of the deboss and the hammer method, while it is an option, is very difficult to control.
Normally, debossing and embossing requires two dies (top and bottom). However, since a 4 ply mat board has some give you probably don't need the bottom die. The die traditionally was made out steel. Today, you can use photopolymer. This has the advantage of being more durable and cheaper. (Google letterpress photopolymer for places that can do it) Many shops can make it from digital files, while others want line art.
There are two major types of photopolymer for letterpress printing steel backed and non-backed. The steel backed plates, while they sound stronger, actually don't work as well on the etching press, because the high pressures tend to deform the plate and the steel prevents the plate from reverting to it's original flatness.
To do the debossing, you should talk to the person in charge of the press in order to adjust it to the thickness of the die and the mat board. It can be difficult to align the die with the board, so an experienced printmaker can help out a lot.
This procedure takes some trial and effort to find the right thickness of plate and amount of press adjustment needed. But with patience, it should work fine.
I've also converted an arbor press (from a machine shop) into a debossing press by machining a die holder and a platform to align the mat board under the die. This works ok-more consistency than the hammer and die, but less than an etching or letterpress.