I want to spray paint a piece of wood blue, then on top of it, put a stencil of map and spray paint that green.
Will the green successfully cover the blue or will the colors combine and become muddy?
It will work fine -- if you wait long enough.
There are two parts to paint setting up. Paint dries like blood. That just means the solvent has leaving it, and the surface is becoming dry. That doesn't give it any strength. Paint also cures like epoxy: the paint molecules are binding together, or polymerizing. That is what gives it strength and durability - what makes it paint and not whitewash. Curing is generally a lot slower than drying.
There are instructions on the paint about "recoat times", or when you should (or shouldn't) add more layers.
If you don't want the color layers to mix, you definitely want to wait til it's "tack-free" and probably at least 3-4x that period. You want it dry through and through. Otherwise, the stencil could imprint onto the paint, or the adhesive you use to get the stencil to lay flat could lift some of the paint off.
Depending on how cheap your paint is, it may take a fairly thick coat to get a true color. You should not spray a thick coat of paint on a stencil -- surface tension will make the paint crawl under the stencil. You want such a light coat that surface tension cannot develop. When that is too tacky to flow, another light coat, again too thin to flow. Don't think anything of painting 3-5 coats - thinner is better. The trick is not waiting so long that your nozzle clogs. Follow the instructions for clearing the nozzle.
You should be able to do this. The success depends on a few factors as follows: