Shoes and pedals don't really "go together".
Shoes are cleat* specific, but are usually compatible with more than one type of cleat.
* the part that is fixed to the shoe which clips onto the pedal.
Each type of pedal has its own type of cleat, which normally comes with it.
Generally, there are two types of pedals. Road pedals and MTB pedals. Which are compatible with road shoes and MTB shoes respectively.
Road shoes are not suitable for walking in for any distance, the cleat sits proud of the shoe, so you'll damage the cleat, and probably fall over.
With MTB shoes, the cleat sits inside the shoe, so that you can walk in them, the cleat will crunch a bit on some surfaces, but it's okay for short-ish distances.
There are also touring shoes, such as the Shimano RT51 shoe, which fit a mountainbike cleat/pedal, but they are similar to a road pedal, in that they are less suited for off-road, getting muddy, etc. But you can still walk in them.
I'm on my first road bike and clipless (they're called clipless because they aren't toe straps...) pedals. I wanted to be able to walk around in my shoes, so I went for the very popular shimano m520 MTB pedal, and a pair of RT51s, and I'm pretty happy with them.
To decide between road and MTB pedals, you need to ask whether you want to be able to walk around in them. Then you can start to think about which brand etc.