On foot
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.
By train
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 (http://www.nankaikoya.jp/...) 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. (http://www.nankaikoya.jp/...)
JR passes cannot be used for the journey; the closest JR station is in Hashimoto, some 20 km away.
By car
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.