Below is a video from a puzzle early on in the game. Anyone who wants to avoid spoilers ought not to watch the video, as it shows how to solve the puzzle. That said, this particular puzzle isn't hard to figure out.
When the player accepts the "A Puzzling Parrot" quest, you may pause the video to read the two pages of the quest description. This explains the story behind the puzzle, as well as hints for the player on how to solve it. The basic premise is that the player must go upstairs to catch the Pirate Captain's beloved parrot, and is given a "Parrot Cage" to do so.
As you can see, as the player approaches the parrot, it flies four spaces in the opposite direction. Should the parrot hit a wall, it will fly away, forcing the player to restart the puzzle. To solve the puzzle, the player must corner the parrot in the alcove to the right.
To answer potential questions about "how the heck does that work in an MORPG?": Each player sees their own parrot. Other players do not interact with your "instance" of the parrot, and because players may walk through each other, there can be no blocking. You might see another person running around the puzzle area, but you won't see the parrot that they are chasing.
The character used here is a female Merchant. As you can see, a Merchant's abilities are named accordingly, and instead of MP, some merchant abilities cost gold to use. Also note that successfully capturing the Parrot requires that you do a lot of damage to it first (ala Pokemon!). Do too much damage and you'll defeat it, meaning that you have to do the puzzle over again.
NEStalgia has many different types of puzzles, most of which are harder or more complex than what you see here. While I'm not going to pull a "Golden Sun" and smother players to death with puzzles, they are definitely an important part of the game.