Once you've chosen a place on the shore, sail your ship there. The building which then appears in the menu is the smallest of the warehouses, and the first building you can erect. It can only be built on the coast. Click on the warehouse in the menu, and then run your cursor along the shoreline. If the warehouse is displayed on the coast, you can build it by clicking your left mouse button. Now you've established a base of operations, and laid the cornerstone of your settlement.