So here's the shoe/pedal rundown.
3 bolt cleats -
Look, Shimano road, some others that I'm forgetting.
These are big honkin' plastic cleats that are a good 1/4 thick. They're triangular, about 2" wide at the base and 3" per side. They fit shoes that have 3 bolt spaces/slots in the soles.
Advantages: fewer "hotspots" on your foot from pressure after many miles in the saddle. Good for roadies, hence they're usually only found on road bikes/road shoes.
Disadvantages: plastic wears out rather quickly if you walk around. You don't want to "walk" around because it's more like "crippled-hobbling" around, can be harder to clip in/out of.
2 bolt cleats -
Eggbeaters, SPD, some others that I'm forgetting.
These are small metal cleats (either steel or brass) that are about 1" square and about 1/8" thick. They fit shoes with 2 bolt holes/slots.
Advantages: smaller cleat = easier walking (you can actually walk in them). They last longer than plastic cleats. Generally easier to clip in/out.
Disadvantages: can lead to "hotspots" (areas of increased pressure on the sole of your foot) after hours in the saddle.
Most all cycling shoes will specify weather they are 2 or 3 bolt compatible, or both.
