And now, finally, we can get to work coloring the ocean.
Hide everything except the ocean layer. (Once you get the hang of it, this becomes optional)
Select the cutouts on the ocean, then invert the selection (CTRL-I).
Go to Adjustments > Gradient Mapping
Immediately, the default hideous black to red to white gradient will be applied. Right click on the darkest color, and select "Change Color". The color wheel will pop up, including your palette colors as added way back in the beginning of this tut.
Select the darkest shade of blue and click OK.
Right-click the gradient bar and select Add Color, and add the other three shades of blue to the gradient, working from dark to light. (You can either remove or change the middle shade of red.)
Leave white as the brightest color.
Now for the fun part. Each of these colors (except the ends) is on a slider, and you can tweak the look of your entire ocean just by shifting them around. You can also check the Reverse Colors box and see what the gradient looks like from the opposite direction; I often prefer to do this with the ocean because it puts my darkest shades out where the "deepest" water ought to be. I also take my continental shelf into consideration, and try to have a decent light colored band around each landmass.
When you're happy, click OK.
Unhide the Ocean texture layer and make sure its blend mode is set to Overlay. Feel free to experiment with different blend styles, opacity, and ordering of layers (texture on top, or under the color, etc.).
When you're happy, you can hide the ocean layers, or leave them visible, and watch your world build itself up layer by layer.