How do I create a color gradient over an image like this? I'd like to keep the background bold enough to see over the color.
You're starting with a regular color image, right? All you have to do is desaturate the source image (the easiest way would be to use an adjustment) and then drag the gradient with the Color blend mode applied.
You might also try doing it without the desaturation step. I don't know about Photoshop, but some of the software I've used produces a different result if there's already color present.