Once you have a layer with your lines on it, you're halfway there. Now you can use the magic wand tool to select areas. After you've selected an area go to Select->Grow Selection and add a couple of pixels so that the selection runs down the middle of your lines rather than along the edge of them.

Now create a new layer (in the layers dialogue) and fill (Edit->Fill Selection) to fill the area with colour.

This will colour over some of the line. To avoid this, keep the lines layer on the top (click and drag them in the layers dialogue). Now set the lines layer mode to multiply - this will only use the black parts (the lines) of the layer and not the white, allowing you to see the colour below.

I hope this helps with the next step.