In turning Sickness from a novel (83k words) into a Visual Novel (120k words & climbing), changes to descriptions and monologuing have been the most prominent.
When the transition first began, I was cutting out huge chunks of descriptive text, because I figured the sprites, backgrounds, etc. would make it redundant.
Similarly, some events no longer needed to be written because they could be replaced by animations, sound effects, changes in expression, etc.
There were also scenes that needed to be rewritten for the purpose of impact (eg. the lines immediately preceding a CG), paragraphs shortened or reworded to better fit the textbox, and a bunch of other rewrites I never saw coming.
Further to that, one thing that I'm running into even now is dialogue vs narration. As a first-person novel, copious amounts of content within Sickness were explored purely through thoughts/monologuing. But as a VN, having the main character talk to himself doesn't feel as engaging, so concepts and opinions are often brought up through dialogue instead. It then became a balancing act; is this conversation dragging on too long? Would this monologue be better as a conversation? Would this conversation feel more natural as narration?
Ultimately, I wound up adding back a lot of the descriptive text and narration. Not all of it, and there's still way more character dialogue than when it was a novel, but enough to make it feel more natural and less like a "generic VN". True, a lot of VNs are more dialogue than narration/description, and some do a damn good job of it. But if you're converting a novel into a VN, then rather than remove the descriptive text or completely rewrite scene after scene, I think it's best to instead work what's already there into a more game-friendly format. Rework anything that can be better done with the new tools at your disposal (SFX, animations, etc.), but don't go hacking and slashing; you can add SFX and still leave the character's summary of what they heard.
Getting back to your question of "How would you go about turning an already written story into a VN?", my process was (and still is) quite aimless, so I wouldn't recommend it... but if I could go back in time, I think a good approach would be to code in some of the story, play through the first chapter or so (even without BGs, sprites, etc.) and see how the progression feels compared to other VNs, then progressively implement stock images (concept art) and edit the dialogue as it feels necessary.
After all, text is easy to edit, art doesn't need to be perfect from the beginning, and music/animation can be added at your whim. So try constructing a scene with creative commons sprites and BGs from the forum, even if you have no intention of using any of them in the final product, and remember the types of changes you needed to make in order for the scene to "work" in the new medium. Rewrite until you're somewhat satisfied, move onto the next scene, and repeat. And when you're done, go back over the entire thing, because by that point your style will have changed and you'll think "Did I seriously write that crap?"

Finished games
-My games: Sickness, Wander No More, Max Massacre, Humanity Must Perish, Tomboys Need Love Too, Sable's Grimoire, My Heart Grows Fonder, Man And Elf, A Dragon's Treasure
-Commissions: No One But You, Written In The Sky, Diamond Rose, To Libertad, Catch Canvas, Love Ribbon, Happy Campers, Wolf Tails
Working on:
Sable's Grimoire 2
