After you meet Marle at the Millennial Fair and use Lucca's Telepod, you find yourself in a strange place.
Visit the Forest
After the cutscene when you use the Telepod, go west to fight some Imps. Then go left again to get to the next area.
After you climb the ladder and cross the bridge, go all the way to the west to find a chest (Tonic). Then go east and south to find another chest (PowerGlove). Be sure to equip the PowerGlove right away.
If you go to the Inn, don't bother paying Toma for information. You don't need it.
Now go west and enter Guardia forest. Go north and east (you can stay near the trees to the south to avoid a fight if you wish) into a grove. You will see two sparkles on the ground. Check the north one to get a Power Tab. If you check on the southern one, you will be attacked.
Next, go north to the mid-section of the forest, and check on a bush that is between two trees. If you get attacked, you checked the wrong bush. If you checked the correct one, a monster will come out and drop a Shelter, which you can use to heal up in places where you can save the game. You can get a Shelter from this monster every time you enter the forest. Go west, staying near the trees to the north if you want to avoid a battle. When you can, go northeast, then go north to exit the forest.
Go into Guardia castle. There will be a cutscene. Don't open any chests inside the castle. If you do, you won't be able to get better items from them later.
You can go west and down the stairs and talk to the girl to heal up. From there, go back upstairs, then go north up the stairs where the queen went, to reach the throne room. Go up the eastern staircase in the throne room, and keep going up the stairs to reach the Queen's room. Talk to the guard and he will step out of your way. Go past where the guard was and talk to the Queen, then step forward when she asks. Walk forward again when something is wrong.
Run downstairs and Lucca will join you. Equip her with the Bandanna. Now you can investigate what happened to the Queen.