Kathmandu (or as Stevens spelled it, Katmandu) is the capital of Nepal. In the '60s, many Americans were fascinated with Eastern orthodoxy and saw places like Kathmandu as beacons of enlightenment. Many young people made the trek, and some high-profile musicians mentioned the city in songs where it was used as a metaphoric Eden, which is what Stevens did here as he sings about finding refuge from Western civilization in a simpler, peaceful place.
You'll find plenty of reports claiming that Stevens wrote this song in Kathmandu (a common rumor has him writing it in a tea house in the Asan Tole section), but there is no evidence that he made this journey. These tales are often found in tourist guides with an interest in drumming up business; Mick Jagger, Janis Joplin, Jimi Hendrix and Bob Marley have also been cited as visitors to the city in various apocryphal stories (note how documented The Beatles trip to India was - a rock star couldn't vanish to Nepal without some hard evidence).
Stevens was certainly there in spirit, however, as Bob Seger would be in 1975 when he released his own song about Kathmandu, also spelled without the H.
This lilting acoustic song is a key track on Stevens' Mona Bone Jakon, which he recorded after a nasty bout of tuberculosis in 1968 that nearly killed him. Stevens became a rising star in 1967 with the release of his debut album Matthew & Son, but was turned off by the side-effects of fame and set out to write less commercial, more introspective fare on Mona Bone Jakon.
A shy 19-year-old Peter Gabriel played flute on this song, the only studio session that he ever did for another artist as a member of Genesis. Stevens recalled to Uncut: "He was timid. I hardly noticed him in the studio. He did these lovely flute parts on 'Katmandu.' That was it - the next time I saw him, he had a whole different persona."