A warehouse is the first building you must build on an island to settle the island. It must be built from a ship that has the required resources on board and is close enough to the coast of an island. An island may only ever have one warehouse at a time.
If your warehouse gets destroyed or demolished, you can build another one on any coastal area of the island not occupied by another player. The warehouse building icon is the last building icon displayed in the peasant building tab of the build menu. This icon will be grayed out if you already have an existing warehouse on your island.
Whether you build an occidental or oriental warehouse depends upon if the ship your using is an occidental or oriental ship.
The initial occidental warehouse always starts as a Small warehouse, and can be upgraded to a Medium warehouse (with the additional requirement of stone) and Large warehouse (with the additional requirement of glass).
There is only one level of oriental warehouse, the Oriental warehouse.