First settled in 816 by the monk Kūkai as a retreat far away from the courtly intrigues of Kyoto, Mt. Koya is located in a 800m-high valley amid the 8 peaks of the mountain. The original monastery has grown into the town of Koya, featuring a university dedicated to religious studies and over 100 temples, many of which offer lodging to pilgrims.
In 2004, UNESCO designated Mt. Koya as part of a wider World Heritage Site
The mountain is accessible primarily by the Nankai Electric Railway from Namba Station in Osaka, which connects to Gokurakubashi at the base of the mountain. Koya limited expresses take 80 minutes and cost ¥1610, while ordinary expresses are lower priced at ¥1210 and take only 10 minutes longer at 90 minutes. The final half of the trip is a slow climb up into the mountains and extremely scenic in good weather.
If you are traveling to Koyasan from Kyoto, you can use a JR pass to get to Tennoji on the Kansai Airport Express train. You will then need to change to the Osaka Loop train and get off at Shin Imamiya, where you can transfer to the Nankai (private) express train. At this point you will need to pay approx. ¥1230 to get from Shin Imamiya to the top of Mount Koya (includes the cable car ride). Depending on the time of day, you may need to transfer at one of the stops before ending up at Gokurakubashi, though if you time your trip right, you can take an Express train straight to the foot of the mountain at Gokurakubashi.
A cable car from Gokurakubashi then whisks visitors to the top in 5 minutes for ¥360. From the cable car station you'll have to take a bus to town (5-15 minutes depending on your destination). Train, cable car and bus schedules are synchronized so this works better than it may sound. Actually, at least some of them are so well synchronized that you only have a couple of minutes in between. So don't count on a toilet break on the station.
A good value way to reach Koya-san is to purchase the Koyasan World Heritage Ticket  for ¥2,780 (express) or ¥3,310 (ltd express) available from the Nankai ticket counter. This ticket includes round trip train, cable car, and all-day bus pass. This ticket works for either a single day trip or for staying one night on Koyasan. Also gives coupons for small discounts to popular destinations on the mountain.
In the spring (April 1 to June 30) and autumn (October 1 - November 30) the 'Koyasan one day ticket' （高野山１dayチケット） may be purchased. This is similar to the ticket above but also includes connection to a single private railway, giving good value for money. For example, Hankyu (¥3000), Hanshin (¥2900), Keihan (¥3000), Kintetsu (¥2980), etc. (Japanese)
JR passes cannot be used for the journey; the closest JR station is in Hashimoto, some 20 km away.
If you have your own set of wheels, you can also head east towards Ise or south to Ryujin Onsen and southern Wakayama. Both roads are small and there is no public transportation, but daring souls might try hitching.
Before the train and cable car connection, which was built in the early 20th century, the only way to reach Mt. Koya was via the ancient pilgrim trail called the Chōishi-michi (町石道) which is still maintained and marked with stone pillars every chō (about 108 meters) - these have given the trail its name. It begins in the town of Kudoyama (九度山), which is a stop on the Nankai train line to Mt. Koya, at the (rather interesting in itself) Jison temple (慈尊院). To reach the temple from the station follow the main road downhill and across the bridge keeping an eye out for the green signage on the left. Note that free detailed English and Japanese hiking maps are available from Jison. If you want to do the Japanese thing, you can pick up a souvenier stamp rally card too - note the 7th and final stamp can only be obtained during business hours.
The trail is about 22km long, ascends about 700 meters (most of this in the first and last quarters) and can be walked in about 7 hours plus resting time, offering a very rewarding hiking experience. In reality, you'll likely want to take the side-detour roughly 1/3 of the way up, adding a third world heritage site on to your journey as well as an extra 2-3km depending upon approach. Local signage claims there is guest house accomodation at this point but this is unconfirmed.
Fire is prohibited, but there is nothing stopping you from camping in one of the observation huts along the way. In fact, like many such huts in Japan, locals have stashed a couple of ground mats in the rafters of one roughly 2/3 of the way up, just past the Yatate Jaya Teahouse.
You can also ask the resident monk at Jison if you can camp on the grounds, if you want to get an early start; there is a little graveled area, just beside the toilets, on which he'll probably let you sleep.
The mountain is home to the following famous sites:
Most (if not all) sights close at 5 pm, so there's only little to do in the evening unless you are staying in a temple.
Hiking around Mount Koya is a good option. Among many courses, there is one that starts at Daimon (大門、big gate), hiking up to a tiny shrine at the top of Bentengaku (弁天岳), and then down to Nyonindou (女人堂). Not a difficult hike, and should take only a couple of hours, depending on how often you stop on the way to take photos. You can encounter a few species of lizards and snakes along the way, such as jimuguri (ジムグリ, Japanese Forest Ratsnake), the Japanese five-lined skink, and the Japanese grass lizard. From the top you can see all the way south to Wakayama city and the ocean.
All temple lodgings on Mt. Koya offer shōjin ryori, purely vegetarian food intended for monks. People who equate vegetarian food with blandness will be surprised - in their hundreds of years of experience with vegetarian cooking, the monks have invented amazingly tasty dishes. A local specialty, Kōya-dōfu, is prepared by freeze-drying and then reconstituting tofu.
For those unwilling to eat vegetarian, a number of restaurants offer regular Japanese and Chinese cuisine. There are also many reasonably priced izakaya around the center of town that offer a range of many traditional Japanese pub foods.
About half of the over 120 temples in town offer lodging for pilgrims, known as shukubō in Japanese. Prices vary between ¥9,000 and ¥15,000 per night and include two meals. You will be offered the opportunity to join in the morning prayer session, a hypnotic experience involving sutra chanting, incense and gongs. Outside the main season, you can just show up at the Koya cable car station and book from there, but generally reservations are preferred. A full list is available here, but note that not all temples are set up to handle visitors who don't speak Japanese.
While the monks don't drink, alcohol is available to guests at dinner, and perhaps even from a vending machine. Temples have set hours at which the front gate is opened and closed, and the time the bath is available. This curfew can be as early as 9 PM, so don't expect to head out after dinner — although you'll want to go to bed early anyway if you want to attend the morning prayers around 5 AM!
If choosing to take the hike up from Kudoyama, in addition to the regular hiking precautions, consider that roughly 1 km of the course runs directly beside a golf course. In addition to stray balls (wear a hat), it seems the owner may be fighting an insane one-sided border dispute because, as of June 2010, around where the trail doubles as an access road, somebody has installed a couple of electrified tripwires over the trail, which appear to be hooked up to the golf links. Be aware.
An otherwise complete set of localised advisories can be found on the English or Japanese hiking maps available at the temple at the very start of the course.
Not far outside Koya, approx. 15 min by car, is Otaki, a small town aptly named for the large waterfalls at its entrance. Once past Okunoin, take the Ryujin Skyline towards Shirahama and look for a small sign about 15 min down the road. The entrance should be on the right. Take the small road downward for about 2 minutes and the 2 large waterfalls should be visible from the road. It is an especially nice place to stop and have a picnic before leaving Koya.