From Shih Tzu's description:
"Cave Story (Doukutsu Monogatari) is a five-year labor of love by a Japanese freeware developer who goes by the handle "Pixel". The game (made for Windows systems, although there's a way to get the translation running on the Mac port) an old-school 2D adventure-platformer in a Metroid-ish, Monster World IV-ish vein. So on one hand, there's lots of jumping and shooting and blasting things (awesome!), but on the other hand, you also get a cool story and no small amount of questing and exploring (awesome!). It's several hours long, it's packed with secrets, it's got pretty pixel art and a neat NES-style soundtrack, and it's totally free of charge.
Pixel says he'd rather people discover the game on their own without any expectations. I'm not Pixel. Drop what you're doing and play this."
There's a full interactive walkthrough on verflaxia.net.
There's also a very good walkthough by ReroRero (Local Mirror 5th Jan '08) hosted on the Miraigamer fansite. That site also has a dedicated walkthrough page, which includes a number of full walkthroughs as well as hacking guides and speedrun guides.
The following video from the Doukutsu uploader shows a speedrun of the hell stage in 2 minutes and 17 seconds, which may be of interest to anyone else planning to do this: