After the Ocean Palace, you'll wake up in a tent in the Last Village. To proceed, head to the Commons. Before you do, seriously considering putting Ayla in the party. She will make the next section much less frustrating.
After returning from the Blackbird, a woman here will ask if she should plant or burn a sapling she was given. Tell her to plant it to set up the Sunken Desert sidequest.