Don't book before you get there. The prices quoted by silent1mezzo are staggeringly expensive, compared to what you can get once you're actually in Peru. Most 5day tours should run for less than $200USD.
The first step is to get to Cusco. You can fly there (landing there is pretty spectacular) or you can get a cheap bus from pretty much anywhere else in the country. Some people have problems with the altitude in Cusco, so planning a couple of days for acclimatisation and exploring is a good idea. There are some short walks to ruins near the city that will help.
There are probably hundreds of tour operators in Cusco (here is a list of 66 that have an online presence, there are many more without one) that run hiking tours to Machu Picchu. Ask around, or at your hotel/hostel for tour company recommendations as they're likely to change.
If you want to do the Inca Trail, it is recommended that you book well in advance (months), as this is so popular. Because of the popularity it is also very well trafficked and apparently not very charming or enjoyable as a hike (I didn't do it, so this is just hearsay). Basically, I would prepare for there to be whinging tourists to be all about you.
There are many hiking alternatives to the Inca Trail which also end up at Machu Picchu. These can all be booked in and leave from Cusco at less than a week's notice.
Salkantay: 5days/4nights, goes high up into the mountains (4600m) and past an unclimbed, snow-capped mountain called Salkantay. Some steep sections. Very spectacular.
Choquequirao: A longer trek (9 days) which includes cultural immersion as well as spectacular scenery. Involves 2 days of trekking back from Choquequirao on the same path, so there are some repeated views.
Cordillera Huayhuash (leaves from Huaraz): A comparatively quiet route offering solitude and scenery, takes one of two routes near the Cordillera Blanca mountains.
Lares: 4days/3nights, Takes in the Quechuan lifestyle. Famous for the textile villages encountered along the way. Crosses two peaks and takes in some hot springs and lakes.
Jungle Treks: Most of these involve a short walk, some downhill on-road mountain biking and a bus to Machu Picchu. Not highly recommended if you like hiking.
DIY hike: Get to Aguas Calientes by train and continue up to Machu Picchu either by bus or by hiking the the five-mile trail. If you get there at dawn as it opens, your views won't be spoiled by the throngs of tourists that arrive later in the day.
I should mention that most of these treks will be fully inclusive of include a tent and mat, food, and guide. Some provide a mule to carry your gear either all the way, or part-way with you. I found this against the spirit of hiking and chose to carry my own pack.
- You can befriend your guides by offering to carry some of the food they are lugging for the group (they will likely refuse, but the gesture is appreciated)
- Ask questions of your guide - I found they were not very talkative about the history or scenery but when prompted had quite a bit of knowledge to share
- Always walk on the high side of mules so you don't get bumped off a mountain
- It gets very cold at night at those altitudes, bring a good sleeping bag
- The sun can be very intense during the day at altitude, bring sunscreen.