dark_dragon_storm

Right, so you've got the border key. Go towards North Ryoshima cost by exiting Sei-An City, turning right and going down to the locked gate. The guards will let you pass when you have the border key. The person you need to talk to on a shore is a boy, who's pretty obvious because he wears a bucket, and is being beaten up by three kids. Knock any of the three children out your way, whomever you feel you want to hit the most, and talk to the Bucker-Boy until he tells you about the messenger of the Dragonians. Follow the hints from there, and you'll progress with the Okami story.

Catching the theif and removing the curses from the trees are optional sidequests that give you praise and little more. Keep in mind you'll need to have aqquired several specific techniques to finally catch the theif and return all the stolen items to people around the city. To remove all the curses from the trees, you must first find all the non-cursed trees and use your bloom technique to make them blossom. A man in the city will then run around removing the curses from the other trees for you to make them bloom.