Every bike has pedals, but the type of pedal that is best for you will differ depending on your taste and your style of riding. Your basic choices are flats, cleats - these are sometimes referred to as clipless, and clips.
FLAT PLATFORM PEDALS
The flat platform pedal is standard on most bicycles. It’s the kind you would have used as a kid. They’re adequate for most types of bike riding, but have draw backs for racing or touring. They come in plastic and metal. The metal ones are either low cost heavy or higher cost lightweight pedals. You also have a choice of a narrow or broad pedal. See SHOES below to help decide which is best for you.
CLIPLESS with CLEATS ( named due to the lack of toe clips )
Cleats or clipless pedals are what I highly recommend for bicycle tours. They do require a special pair of shoes though. See SHOES below. Cleated pedals will allow you to pull up on the pedals as well as push down. Pulling up will place your legs in a perfect circle, allowing you to pedal in a higher gear, which means you will go faster. They also offer better muscle use: pushing down focuses on your quadriceps while pulling up uses your entire leg ( including hamstrings ). SPD mini cleats are what I choose for tours. They make it easier for you to walk around. Some people prefer a pedal that is flat on one side and cleated on the other, so they can still ride without special shoes when they want or if a cleat breaks on their shoe. Make sure to get a wider pedal system with float. Float allows your foot to move side to side, which will help minimize knee problems. MKS offers a removable pedal that can be used as a theft deterrent. However, any style of Shimano, Crank Bros, MKS, or VP pedals with float should be fine. These companies have been producing pedals for decades; hence their products are very mature. I don’t recommend house brand pedals such as Forte and Nashbar because they have been known to have problems.
If you use flat pedals there is no need to buy special shoes; just choose a brand of shoe that has a reasonably stiff sole. A stiff sole can help you allow blood to flow reasonable well to your feet so you don’t get that pins and needles effect. That feeling is often felt with too soft a sole on your shoes because your foot bends too much.
If you buy a pedal set with cleats or clips you will need to also buy a pair of shoes that accept those SPD cleats or clips. I do not recommend buying shoes by mail order, unless you are certain of your size for that shoe brand. Shoes need to be tried on to see how they fit. I also don't recommend buying high end carbon soled shoes; they are very stiff and uncomfortable. If you get a shoe with nylon sole it will flex giving you greater comfort. I feel that laces on cycling shoes are annoying and too dangerous; I prefer multiple Velcro straps on my shoes.
If you are planning on doing a lot of walking as well as tour riding, I recommend that you bring along a light pair of walking shoes. Cleats and clips make a lot of noise on hard surfaces and the stiffness of the soles makes walking less comfortable.