First off, Searching the forums can be your friend. There are several threads about this subject
As for your answer...
1. Port royal, big gray stone building at the top of the big hill.
2. Crates and barrels scattered about the fort
3. See # 2
When you walk up to a crate or barrel, a green circle will appear at your feet, and you will be given the option to "press shift to search" Press shift, your pirate will search said crate or barrel, and if your quest item is located, it will be updated in your journal.