We have looked at bike pedals and why they make a difference to cycling performance. Well it is not possible to use these effective bike pedals without having 'proper' cycling shoes!
The way they work is that a cleat is screwed to the bottom of your shoe, and then the cleat in some way clips onto the pedal. The exact process varies slightly, depending on the make of pedal and cleat, but generally the front of the cleat is put into/onto the pedal first, and then pushing down with your foot 'clips' the rest of the cleat into the pedal.
This is easier to do than to explain. The front of the cleat is put against the front of the pedal. The rear of the pedal, on being pushed down, forces a spring to open a little, and the cleat snaps into place.
Clipping to the first pedal is easy because you can be stationary. To do the second you need to be moving! It becomes second nature with a little practice.
The first thing to practice is removing your feet from the pedals. This is done by turning your heel away from the bike, which slides the cleat neatly out of the pedal. Easy, but again needs a little practice - remember, you can't just lift your foot back off the pedal.
So that means you need special bike shoes that are made to have cleats screwed onto them.
Note that cycling shoes last for ages, because they are almost never called upon to actually walk on the ground! Indeed having a cleat fixed to the bottom of your shoe, and a very rigid sole, makes walking extremly awkward. It is possible to buy 'cleat covers' which make walking a little easier (and help protect the cleats from damage).
Some people carry a small screwdriver in their toolkit, so if they need to walk a long way (eg because of a problem with the bike) the cleats don't make this impossible.
Your main considerations when choosing a shoe for cycling will be rigidity (and aesthetics) rather than weight or how aerodynamic the shoes are, although these both play a part. Airflow through the shoe is also important and most have some breathable material near the front to help this.
Some of the newer shoes have special soles constructed from magnesium or other exotic substances, some use carbon-fibre, and others (most) make do with more 'traditional' plastic type soles. The important think is that they are rigid - your foot shouldn't be flexing like in a 'normal' trainer.
Ironically, this can often mean your feet become rather cold, since they are remaining immobile and have air-vents to allow air to circulate. Oversocks and special inside socks are available if this becomes a problem.
A full selection of cycling shoes can be seen (and ordered online) at Evans Cycles.