I had a hard time understanding Cave Story until I personally decided that Cave Story is a sequel to the NES game Crystalis [aka in Japan, Godslayer: Sonata of the Far Away Skies]
By incorporating that story into Cave Story's history a lot of things made more sense and a lot seemed to click in my opinion... lol
Crystalis would take place hundreds or thousands of years before Ballos' kingdom... but it helped me get comfortable with how Cave Story's world is the way it is...
Check out the intro's first 2 minutes or so :
http://uk.youtube.com/watch?v=76gCa2PIbys&fmt=18
Check out the ending :
http://uk.youtube.com/watch?v=_KQCqKYjlI0&fmt=18
Just a couple brief notes of the game :
The main character is from the past, he's been sleeping and he awakes with no memory...
But, quickly destiny is thrust upon him as he travels the world and recieves messages from his counterpart who has also awoken... Mesia. [seems strangely close to Misery...]
The main character over the course of the game develops the power to levitate, to teleport, to paralyze, heal himself, cure himself, change enemies into lesser forms [like blobs etc], and a barrier to protect himself. He wielded swords that he could use to channel magical attacks, like lightning bolts, fireballs, ice, wind...
I wrote a lot more on this thread about it though :
http://www.cavestory.org/forums/threads/152/
Jump to the bottom of the page to see an interesting comparison screenshot. [there are quotes from the game right above that]
I really want to see Cave Story and Crystalis as part of the same storyline because Crystalis always begged for a remake or to have more in that universe... I just wonder if Pixel played Crystalis in his youth