From the Super Mario Wiki
The Post Office is located east of Princess Peach's Castle in Toad Town. Parakarry and the Postmaster work here. In Paper Mario, Mario and his party can come here to read mail that was posted during the course of the chapter. The mail received is only for Mario's party, while mail for Mario himself is delivered to his house and can be found by his bed.