The Visual Novel engine is the first step. Personally? I recommend Ren'Py, the most popular visual novel engine for English speakers. It's easy to use and the programming language is pretty cut-and-dry until you start getting fancy with it. But then you have lots of people you can ask questions to, no?
Ren'Py uses a lot of shortcuts that make things easy. Each character in your novel will have a different look and style. All you need to do is pre-program shortcuts into your code, and it reduces the copy paste or typing you have to do. For instance:
Do you see on the far left side of the screen the green lines that start with "L"? "L" is a shortcut I created for my character "Lance". That way, by typing "L" into my code before a quote, the program inputs this for me:
define L = Character(' ',
color="007FFF",
show_two_window=False,
window_background="lframe.png",
window_xanchor=0.0,
window_xpos=0.0,
window_yanchor=0.0,
window_ypos=0.0,
ctc="ctc1",
ctc_position="fixed",
window_left_padding=200,
window_top_padding=420,
window_right_padding=30)

This automatically accesses the special text box I created for him, anchors it in the correct location, inputs the click-to-continue indicator (usually an arrow in most games that indicates you can advance the text), and the exact location where the text should sit. Simple! (-ish)
If I knew how to create a video, I would, because the code I have here also animates the sprites. Their mouth flaps (called LipFlap in the coding) when the text advances so it looks like they're talking (you see this in the Ace Attorney series, but it is absent in games like Trauma Center).
Another aspect that makes Ren'Py awesome is the packaging. With a few clicks, the program packages your game for you (after running LINT, an error-checker). Note that LINT is not a substitute for thorough testing, as they will remind you. Once your game is completed and you're ready to release it (or a demo, depending on what you want to do), the packager will automatically create distributions for Windows, Mac OS, and Linux, together or separate depending on your preference, zipped up into a single file and ready for launch. The completed game will not require installation, it will be a stand-alone game that can be accessed.
Ren'Py also supports rollback, text skipping, and other features that are fully customizable. Ren'Py can create games for PC, Mac, Linux, and Android, but the Apple Terms of Service prohibit you from creating a VN on their app store unless you pay them, so Ren'Py does not have a distribution for iPhone, iPod Touch, or iPad.
Ren'Py Web Site:
http://www.renpy.orgThe Ren'Py framework software is free for download.