While in the Tenda Village, you get a call from Apple Kid, and then you hear him get kidnapped. You go to Winters to investigate.
Investigate the Disappearances
When you Teleport in to Winters, you find Maxwell, who says Tony is missing, too. If you didn't erase the Pencil Statue here in Winters earlier, get Escargo Express to send you the Pencil Eraser.
Head south toward Dr. Andonuts's Lab, fighting aliens along the way. If you talk to the Tessie Watchers, you'll learn that one of them has gone missing, too. Talk to the Bubble Monkey to get Tessie to take you across Lake Tess.
If you have the Pencil Eraser, or if you already erased the pencil statue, you can avoid Brick Road's dungeon. If not, it's not a big deal. Just go through the dungeon.
Go to the lab. Only Apple Kid's mouse is there, as well as the friendly Cave Boy. The mouse will give you the Eraser Eraser.
Go north to Stonehenge and step on the small circle in the center. Descend the ladder and make your way in. Use the Eraser Eraser to unblock the path. This is Stonehenge Base, and it's quite a tough place!
Sword of Kings
Stonehenge Base is home to an enemy that, in rare cases (1/128) will drop a Sword of Kings, which is the only weapon that Poo can equip. The enemy is Starman Super, and they will all disappear once you defeat the boss here.
Starman Super are most plentiful in the first 'warehouse' area of the base. A good place to try for infinite respawns is around the bridge where the Broken Harmonica can be found.
Watch the movement pattern of Starmen carefully. Rather than moving in a straight line, they teleport from place to place at a fixed distance. By watching how they move, you can consistently surprise attack them. Furthermore, if you equip Ness with the Casey Bat (being sure to switch back to a better bat during battle with the Use option,) you increase your chance of an instant win against Starman Super, making your effort to find the Sword of Kings go more quickly.
Avoid the Atomic Power Robots if you can. You'll have to put up with fighting regular Starmen, because there's no difference between its overworld sprite and that of the Starman Super.
Depending on how quickly you are able to defeat Starman Supers, it could take you anywhere from 45 minutes to 1.5 hours to snag a Sword of Kings. In other words, don't bother with it unless you're truly dedicated.
Get Through Stonehenge Base
From the Eraser Eraser spot, head southeast. After going through a door, head along the narrow passage, and then go right when the path widens. There is a narrow path just right of the rectangular "hole" in the ground.
Follow this path until you reach a gift box with the Spicy Jerky. Head right. After going through the door, you can use the narrow path on the right side of this room to get a Guts Capsule. Since it's kind of a long walk, though, you can skip it and get it later.
Go south in the Guts Capsule Room (the one after the Spicy Jerky room), and in the next area, when you reach a spot with two narrow paths, one going up and the other going east, you can take the one going up to get a Cup of Lifenoodles. Otherwise, go east.
Soon you reach the first warehouse area. As stated above, this is the best place to try to get the Sword of Kings.
You can go east from the warehouse entrance to find the Broken Harmonica, or you can skip it and come back for it later, when there aren't any enemies around anymore.
When you go down the ladder just south of the warehouse entrance, you'll find a PSI Caramel along the way, and from there the path is straightforward until you're past the Exit Mouse room.
After you go through the Exit Mouse room and reach the dark area, you can go right from the entrance to find the Broken Trumpet. Or, you can skip it and come back for it later.
Going north from the entrance to the dark room, stay along the left wall until it curves around. The path splits off three ways. Going to the right gets you a Speed Capsule, and going to the left gets you the Pixie's Bracelet. The middle path will take you to the next room.
In here, you'll find all of the missing people floating in liquid-filled tubes. They're all pretty sad about that. Apple Kid is there, and Dr. Andonuts, Tony, and others. Hurry along to the room to the right.
Starman Deluxe is in here. Once you defeat it, you won't be able to try for the Sword of Kings anymore, so keep that in mind. Find out how to defeat Starman Deluxe.
Once Starman Deluxe is dead, the base will permanently shut down. Exit left to find that all of the abductees have been freed from their prison capsules. Ask Apple Kid about the shyness book and he'll say that he already returned it to the library. I guess you'd better go to Onett!