It seems to me that the question isn't so much about punishment as it is about identifying the person who committed a crime. If you're just after punishment options, there are a number of options above. But before you can punish someone, or even track down the culprit, you have to figure out who the culprit actually is.
The first problem is that you can't use normal tracking methods when the offender can both enter and leave the scene via teleportation. Unless there's some detectable pathway left by the teleport there's no realistic way to follow the offender's path. Of course if teleportation exists then a tracking ability may also exist.
Assuming there's no realistic tracking option we're limited to the evidence available at the scene in order to identify our offender. Some of the comments seem to indicate that we're in a low-tech world at best, so advanced forensics techniques like DNA profiling is out. Instead we're going to have to rely on low-tech things like witnesses. Sadly, criminals are well aware of the standard means of identifying them, so they routinely wear disguises or simply cover their identifying features.
Under those conditions I suspect that criminals will never be caught after the fact. The only time they will be brought to justice is when they are rendered unconscious or somehow unable to escape prior to leaving. Once they're gone, they're safe.
To that end, a society would need to develop some good ways of disabling teleporters. This might be as simple as a gas that produces disorientation or unconsciousness. I imagine that this would become a popular personal defence, like current capsaicin sprays.
Or maybe there's a way to disrupt the ability using some sort of electromagnetic field. A big electromagnet that can be pulsed to disrupt the teleport could also prevent them from leaving, and would probably be used to protect valuable or sensitive locations. The security field from Sanctuary (the TV show) is an example of this.
Once disabled the offender would have to be restrained somehow. I have a bunch of ideas about that, most of which are in the other answers so I won't go into all of them here. Replacing a vital section of a major artery with a device that can be used to track or kill the teleporter remotely would probably be a good permanent solution.