Big Bob is first found in the second to last section of the Restwater Valley level which involves rescuing bunnies from cages. If you have been talking to every NPC, you will find him pretty quickly. Make sure the exclamation box above his head is grayed out to indicate that you talked to him.