If you obtained the Space Suit and the Space Compass from the Lost Palace, then you are ready for the next stage of the adventure. Head back to the Forest City and rest up. If you happen to talk to people there, not many of the residents have new things to say, but some of the older residents will begin to talk about the early race that walked across Fairyland known as the Sarah.
The computer memory in the Lost Palace mentioned a crack in the ground. If you explored enough of Fairyland, you will have no doubt encountered the giant crack in the ground, which is located two screens south and several screens west of the Forest City. Make sure that you have the Space Suit equipped, and then try jumping into the crack. Doing so will send you to... space.
The image shown above is only the small portion of that surrounds the lost Spaceship. Space is actually quite large, over 30 screens in every direction. And most of it is empty and unremarkable. To travel through it, you appear to simply "walk" from one screen to the next. Spaceis occupied by the Guba enemies that you met in the Lost Palace, along with knight-like enemies known as Garbas. Neither one make for particularly good level grinding targets.
Instead, you should focus on finding the Spaceship. To do that, you'll need to use the Space Compass. On each screen, try using the Space Compass. An image will appear pointing in one of eight directions. If the compass is pointing diagonally, go to the screen it is pointing, and use the compass again. Once the compass is pointing in one of the four cardinal directions, you can simply walk in that direction until you actually encounter the Spaceship. Once you arrive, duck in through the entrance along the right side of the ship.
The Spaceship is like a large dungeon. It is occupied by three different types of creatures. Of those creatures, only one is good and should not be killed. That would be the bird-like Sarahs. The other two are evil and can be fought, including the Garbas which you encountered outside of the ship. The new evil enemy are the Guyzers, which shoot powerful beams. They are worth a lot of experience points if killed. Consider casting Invincibility if you have it.
The big discovery inside the ship is the memory banks located in the lower left corner of the ship. They spell out the next steps that you must take in order to continue your adventure. The Sarah lament that they have almost all turned into monsters, and Kaizack is the one responsible. They believe he is found in an alternate dimension, which you need a talisman to enter. This talisman is said to be in the Cave of the Dead, 7 steps south and 4 steps west of a wall that contains ruins.
There are three treasures that you can obtain here, and one is very important. The important treasure is the Horn, which can be found in the upper left corner of the ship. It is a key item that you'll need later on. One of the chests contains the Fairy Helmet, the best helmet in the game. In Super Hydlide, it can be found in the upper right corner of the ship, although the computer versions position it more towards the bottom of the ship, as shown in the map above. The last treasure chest is near the middle along the top, and it contains a Long Bow. This is a powerful ranged weapon, that is stronger than the Broad Sword, but also a little heavier. You may be over burdened if you pick it up, and you'll have to decide whether to throw it away, keep it and throw something else away, or try to suffer with it until you can sell it at a shop. You can also cast the Weight spell for a temporary reprieve.
Once you have gathered the information about Kaizack, and you've got the Horn in your possession, you're essentially finished. There are escape pods along the top of the ship which, if used, transport you back inside the Lost Palace. However, it's easier if you cast Move to send yourself back to an Inn. At this point, you can drop the Spacesuit. If you find you're ever in need of one again, you can always collect another from the Lost Palace. You should teleport back to the Subterranean City, as you'll need to go back to its cave next.