I'm currently reading Egil's sage and with all the crossing from Norway to Iceland to England and to the Baltics, I've noticed one common denominator when it comes to the ships. It seems that the author puts great emphasis on ships being painted above the plumb line.
Why is that? What does it mean? What is a plumb line on a ship? Why would the author mention this, or is it more of a memory filler like when Homer talks about wine-coloured sea?
It seems that a plumb is used to find depths but would it have been lowered from the decks or from within the boat? Is there something that would help me to understand these ships' structure better?
A plumb line is used to measure depth. It is not a part of the ship structure, but simply a line with something heavy on the end, and lowered from the deck. The seaman holding it would feel when it hits the bottom, and there should be markings on the line, marking the depth. With no markings, a seaman might also count fathoms by stretching the line to the full length of his fathom before lowering into the sea.
Ships in the North Atlantic archipelago seem to have been brightly painted during the Viking Age. In this case, 'above the plumb line' seems to be a poor or possibly erroneous translation for 'above the water line.' A plumb line, as you mentioned, is a string with a usually lead weight attached for measuring depth, but sometimes it's used to refer to straight lines, for example when wood is cut along a plumb line. In this case, however, neither use seems appropriate for the context.
Experimental archaeologists who have built replicas of Viking-Age boats often use contemporary illustrations to help figure out what these kinds of references mean. In particular, the Bayeux Tapestry has proved very influential. The tapestry is essentially a really long cartoon embroidery showing how William the Conqueror took over England in 1066. It was probably made in England about 10 years later, so it's taken as a fairly accurate depiction of North Sea ships at the very end of the Viking Age.
In particular, check out the boat-building and fleet sailing scenes. Taking this as inspiration, modern archaeologists and ship builders have settled upon paint jobs that look like this or this. Cool stuff, huh?