I'm about halway through Celestia. At first it does seem like random quests, but the further along you get the more it starts to tie together. At Stormriven it starts to reveal itself a bit. It just takes a little bit of time.
Celestia's plot is that it is an ancient scientific civilization that has been destroyed by a watery cataclysm. It has been invaded by the evil shark race, in the early stages you are pushing back the sharks. Eventually you meet some ghosts that are all that remain of the original inhabitants. The sharks, however, are less troubling than the shadowy buglike creatures you will eventually learn are the minions of Morganthe, who has turned some of the ghosts to her side. The overarching story is that you are freeing Celestia of its invaders and giving peace to its ghostly inhabitants. Celestia also serves to introduce the astral schools of magic.
actually celestia does, if you read the dialog that the npc's give you then you'd figure out that it comes in with the morganthe ark. to sum it up, morganthe wants to use the celestial magic to conquer the spiral, but theres another its a place underwater in a huge dome surrounding them and they've found this magic called the arstral schools and that morganthe wants to take the magic for her own bidding, thats bout it. anyway celestia actually does have one just saying :)