The goal here, although it's not made apparent right away, is to find the person standing near Pax Tharkas.
You start the game in a field, near a person. You can talk to him or any of the other people standing around if you want some more of the story. One of them passes you a potion of healing. The fortress is far to the South East so you have a fair bit of walking to do. Start by going South until you reach a river going in a West-East direction. Follow the river West until it ends and then continue South until you see another person standing around. Talk to this guy and he'll give you an item. After that, turn East until you reach a large body of water, an ocean presumably.
The guy you run into on the way talks about Verminaard, the commanding officer of Pax Tharkas and an important part of the story. Now, start walking South again, along the coast until you reach the treeline. Make your way through the trees, staying near the coast when you can, and you'll find Pax Tharkas and the guy standing near the fortress. You don't need to wander elsewhere unless you want to talk to the various people scattered about. Talk to the guy and the game will go to a short cutscene.