You are close to the solution, you merge the vertices at each end of an edge to remove the duplicate edges.
If you look closely at your first screenshot, the two edges don't line up exactly. when you use Remove Doubles, it has an option defining how much distance between two vertices is considered a duplicate vertex. The default is 0.0001
- which means really close together. You can press F6 to adjust the value, but too big a value will start merging vertices you don't want merged. Only the current selection is considered when removing doubles, so check that you have edges using the duplicate vertices selected.
When vertices are further apart it is better to manually either move them together, or merge them.
Blender has transform snapping settings that lets you easily snap vertices/etc to other items. Set the snap element to vertex and either enable snapping or hold ⎈ Ctrl when you want to use it, and as you move the cursor close to a vertex it will snap and draw a circle around the vertex it is snapping to. After moving with snapping enabled you should find the remove doubles working without adjustment. There is also an auto merge option that will merge vertices as you snap them together.
You can also manually merge specific vertices by selecting both and pressing ⎇ AltM->At Centre - Note that in edge select mode, using merge at centre will collapse the selected edges to a vertex in the centre of the edge, not just merge the vertices at each end.