I know that in my prefecture at least, single and multiple re-entry permits are obtained from the immigration office, and paid for using a really expensive stamp from the post office.
In our case, said office is in the same building as our customs office, and is in a city that's not the main city of the prefecture.