a) How many Kisekis are on PC, and at what point did they jump to handheld? I know that after Sora no Kiseki 3rd there's Zero and Ao (heck's an 'Ao'?), and then there's the offshoot Nayuta and also the two Sens.
The "Ao" in question is a fancy kanji for "blue," with the commonly-accepted English name for the game being Trails of Azure (or Trails of Blue, if you're uncouth).
At this point, every Kiseki game is on PC in one form or another except Nayuta and Sen.
Falcom themselves released the whole Sora no Kiseki (Trails in the Sky) trilogy on PC first and foremost, porting them to PSP (and later PS3) afterward. The PS3 version has the same content as the PSP version, but with enhanced graphics and... 3D TV support?! Which I can't even imagine...
Zero no Kiseki and Ao no Kiseki were next, and were released as PSP exclusives initially. They were later ported by a third party to Vita with enhanced everything (better resolution, rearranged soundtrack, full voice-acting, added minigames), and the original PSP versions were straight-ported to PC by a Chinese developer (with no additional content). Falcom themselves later back-ported the Chinese Zero no Kiseki release to Japanese PC, and presumably will be doing the same with Ao no Kiseki (I can't remember if they've announced that or not, but it's almost inevitable that they will if they haven't yet).
As for Nayuta no Kiseki, that was released as a PSP exclusive and has no ports planned or announced yet as far as anyone knows. And Sen no Kiseki is a PS3/Vita exclusive at the moment.
Do their storylines intermesh with Sora's? Is there a timeline?
Every game in the series is connected, yes, with the solitary exception of Nayuta no Kiseki -- I think everyone is mostly in agreement that that's pretty much Zwei 3, they just called it Nayuta no Kiseki so it would sell better.
It's kind of like a Final Fantasy Adventure situation, I'm guessing.
There have been some hints and theories recently that there MIGHT be a connection between Nayuta no Kiseki and the proper Kiseki franchise, but I'm kinda hoping that doesn't happen, because Nayuta no Kiseki's world and characters would just... raise way too many questions if they were part of the proper Kiseki universe (and not in a particularly good way).
b) Besides the improved UI and IQ, what else do the Kiseki remasters on PS3 change from their previous releases (remastered music?), and how many are there?
No remastered music -- they're the same games as the PSP versions, just with enhanced visuals (on par with the PC version, more or less) + 3D TV support.
-Tom