If you go with SPD cleats, you can use any shoe that supports two hole cleats - most will say SPD compatible, easy to Google search. You will usually find SPD compatible shoes listed under Mountain Bike shoes if you look at manufacturer sites.

You can spend a wide range of $ on shoes, your first time out I'd start out at the low end. You will find different types of closure mechanisms, with good old fashioned shoe laces the least expensive, next up Velcro, then ratcheting arrangements, then dials and wires (often called BOA). Once I went away from laces, I never went back but I do still have my first pair of SPD shoes that are lace up.

You will see many that have very aggressive soles, like hiking boots - those are really aimed at mountain biking. Then you will see many with pretty flat bottoms, intended for rail trail/road/gravel riding,

I've had good luck with Specialized and Shimano shoes - both are often on sale at REI, too.