Generally, the LOK (LOOK?) cleats are larger and the pedals will have the appropriate receiver.
PSD cleats are smaller and will need the proper pedal for it.
That being said, I've never seen a problem mixing brands as long as the style/type of cleat/pedal are common. Did that make sense? Match the cleat to the pedal and the brand "probably" doesn't matter.
No. for example, a shimano spd cleat (mountain style) will not work with a crank brothers spd pedal and vice versa.
now, if you have different shimano spd pedals on two bikes, then you can use the same shoe/cleat combos for that. because they both use shimano spd system.
but if you had one shimano pedal bike, and one Crank brothers, then you would have to change the cleats on the shoes, or have two pairs of shoes with the appropriate cleats.
also, shoes are designed specifically for road or mountain. some like sidi, have adapter plates to change from road to mountain, but you can't really go from mountain to road on anyone's shoes that i know of.
also, some road shoes, like specialized, come with hole patterns for both road and mountain on the same shoe, though walking on a road shoe with a mountain cleat is asking for a rolled ankle.
I would say to just go to a bike shop and have someone there show you all the different cleats and pedals. I think that would be the easiest way to get your answer by visually seeing what fits together.
With the variety of pedal/cleat combinations that are out there, going into a bike shop and asking to see the different varieties would probably work best. You'll be able to see how the different combinations work and ask all questions that come to mind.
I build lots and lots of bikes and I will endorse a very simple combination that I like a lot and pedal-wise is part of every build unless someone gives me a compelling reason why-not.
The Shimano SH-MT21 All Terrain Shoe
Forte Campus SPD pedals
I should emphasize I have specific reasons for this, and my style of riding and needs for bicycles are likely different than yours. I don't race and have no need for shaving 10 grams off of my pedal spindle or whatever, but I do ride 200 to 300 miles a week all year long, and I abuse the crap out of everything that I set eyes on.
The shoes are comfortable, the cleats barely protrude above the rubber soles so you can walk on all floors without problems, and they are cheap! $40-50 in general. They take a variety of mountain type pedals, so you could get the cleats for Crank Bros for example and put them on, but they come with Shimano style SPD cleats and that is what I use and that comes with the corresponding pedal I like.
Forte (Performance's component brand) Campus pedal are a two-sided pedal. One side is with a SPD clip system and the other side is just for regular shoes - no clips. The reason I use these is that I vastly prefer cycling with clips, but there are times I might want to hop on my bike for a quick trip not involving changing into cycling shoes.
The bikes I build are for people to ride in our tours or do showings on their bikes and the average person borrowing a bike is not likely to walk in here with SPD shoes on.....generally you have the bike before you buy the bike shoes. Therefore, the pedals are super-useable for all of our rides, but also could be ridden with clips.
Anyway, that's my two-cents. This has been derived after many attempts at different clips, shoes and pedals, but of course, I have the above stated perspective.
Shimano SPD cleats will work on Shimano, Wellgo, or VP mountain pedals, although the Wellgo and VP pedals only have half the float (4 degrees vs. 8 degrees) of the Shimano. I have Wellgos on my own bike.
There are several pedal/cleat systems available. the most common ones are LOOK (road bike only), SPD (mountain), Crank brothers (aka eggbeaters) (mountain), Time (mountain). The pedals and cleats will come together, the shoes are separate. An LBS will install the cleats onto shoes for you if you purchase them there. Most shoes are designed to take different brands of cleat, but make sure before you purchase the shoes that they work with the cleat.
Unless you race, and I mean seriously race, I would say to go with a mountain style pedal and good mountain style shoes. They will hold up better, be easier to clip in and out of (especially in poor conditions), and are easier to walk in.
I personally use spd pedals for both my road and mountain bikes. One my road and mountain bike I have double sided spd pedals since I only use these bikes clipped in and I like not having to check what side of the pedal I'm on or worry about mud clogging up the pedal. On my commuter/touring bike I have the pedals with a platform on one side and spd on the other. As others state this allows you to hope on for quick trips, but still have clipless (75% of the time I change my shoes).
The shoes I use are bontrager mtb shoes with a high quality carbon sole that is very stiff. This means I get all the value of a stiff road shoe with the walkability of the mountain bike shoe.
Go into a shop and try on shoes to see what is comfortable for you.
Look at all the pedals available, and ask people you see when you're out riding what they think about their pedals.