Henry handles the spade like a spear. It is a powerful weapon that deals high damage, can strike multiple enemies grouped together at the same time, though it is slow to use. When Henry is about to stomp on a weakened enemy he will stab the spade in the enemy and then stomp on it further, burying it into the beast. Regular enemies will grunt twice when stomped, which would seem to indicate that they are painfully impacted twice. Patients still require to be stomped twice to be killed for good, even with the spade's two-strike stomp.
The weapon is found in the Building World when Henry gets to the large elevator. To get it go to the elevator's control panel and press the top button, then go to the door and go through the hall to find it. It is located next to a Sword of Obedience.