How to add a node/vertex in a QGIS edit session?

With the Node tool (called the Vertex Editor in QGIS 3.0+) selected, simply double-click on a line segment you want to add a node to

If you're having trouble getting the little cross to pop up on the segment you want to add the node to, check your snapping tolerances. Mine were too high, making it impossible to get it on shorter segments. Go to settings > options > digitizing > snapping > "search radius for vertex edits" and set it to something like 10 pixels. Mine was set to 100 map units because I am silly.