In common usage, the terms are interchangeable, though at least in my experience ‘shovel’ is preferred over ‘spade’ in American English (I suspect this has to do with ‘spade’ having significantly more alternative definitions, including possible usage as a racial slur and a handful of uses in animal husbandry that are often not listed in dictionaries).
In technical usage, there are differences but they are subtle.
Formally, a shovel is an implement used for moving loose material such as dirt, gravel, concrete, or snow. The blade (the part that actually holds the material) is usually turned up at the back and sides to prevent whatever is being carried from falling off. The leading edge of the blade may be curved or may be straight, depending on what is being carried. The leading edge of the blade may be sharpened (for example, on a snow shovel, where the sharp edge is used for breaking ice), or may not.
A spade, in this context at least, is an implement used for digging holes. The leading edge of the blade of a spade is almost always sharpened, and may be either straight or triangular (but almost never curved, as that is not especially useful for digging holes), and the blade is typically mostly flat, though it will often have a short section at the back that is bent 90 degrees so that you can use your foot to apply extra pressure to cut through roots when digging with it. Spades, by their very nature, are also inherently shovels (you have to move the dirt out of the hole somehow).
It’s also worth noting that these days, most shovels made for gardening are also spades, because there is generally no need to have a distinct tool just for moving dirt. By the similar logic, most folding shovels, camping shovels, and entrenching tools are also designed to serve both roles.