Is there a way to do a color replace but as a gradient? Fireworks, Photoshop, etc.?

[goose756]

I have a black and white pattern and I want to the black to fade from black to teal, top to bottom as a gradient. Any suggestions?