Wakayama can be accessed on the JR Hanwa Line and the private Nankai Main Line, both of which run south from Osaka City.
JR Wakayama station can be reached by Limited Express trains from Shin-Osaka station, departing every hour. The Kuroshio, Super Kuroshio or Ocean Arrow run from Shin-Osaka to Wakayama in one hour at a cost of ¥2660. From Tennoji the run takes about 45 minutes (¥2280). There are also five daily Limited Express departures from Kyoto (90 minutes, ¥3660). From major stations on the Osaka Loop Line, regular Rapid trains run to Wakayama every 20 minutes: look for the Kishiyuji Rapid (紀州路快速). It takes about 90 minutes from Osaka (¥1210) and one hour from Tennoji (¥830). Be sure that you are in the correct car, as part of the train splits off to Kansai International Airport.
The above trains are free with the Japan Rail Pass.
Nankai Railway has two stations: The main station, located marginally closer to the castle than JR, is called Wakayamashi. The other station, Wakayamako, is adjacent to the Nankai Ferry terminal where ships operate to/from Tokushima. Wakayamashi is served by Nankai Railway's Limited Express train, appropriately called the Southern. Trains depart every 30 minutes from Nankai Namba station, running to Wakayamashi in about one hour at a cost of ¥1390. Select trains continue on to Wakayamako, five more minutes away. By regular train it takes 75-90 minutes to reach Wakayamashi with a change of trains required enroute, at a cost of ¥890. All trains pick up and discharge at Shin-Imamiya station, which is a stop on the JR Osaka Loop Line.
An overnight bus service operated by Narita Kuko Kotsu runs daily from Keisei-Ueno station in Tokyo and Yokohama station in Kanagawa to JR Wakayama and Nankai Wakayamashi stations. The one-way cost is ¥9000 from Ueno and ¥8600 from Yokohama.
Buses run between the two train stations which pass the castle. The maximum journey is 220yen and takes ten minutes or so. Taxis also operate in large numbers, and are very easily found.
In order to experience what Wakayama has to offer, you must explore outside of the capitol city of Wakayama City.
However, the city itself does have a large temple called Kimiidera which is worth visiting. It boasts the largest wooden Buddha in Japan. There's also a post-WWII reconstructed castle (400 yen admission), which is scarcely worth the time that you could spend elsewhere.
There is also a fish market called Marina City, where you can eat fresh tuna (maguro).
Wakayama is particularly mountainous and the JR train lines trace the coast, providing breathtaking scenes of dramatic, rocky coastline bordered by lush, green mountains and pastoral small towns. The ancient Buddhist pilgrimage route connecting Japan's most sacred temples and shrines, the Kumano-Kodo, winds through the mountains here.
To the east of Wakayama city, is the famous sacred mountain Koya-san (高野山）, the birthplace of the Shingon Buddhist sect and the largest cemetary in Japan: a place of moss-covered otherworldy beauty and burial place of feudal lords and samurai. Temples dominate this town, which still revolves entirely around the acitivities of the temples. Koya-san was founded by the Kobo-Daishi, a figure known to all Japanese and credited (but probably not actually responsible for) many legendary feats such as inventing katakana. Koya-san is easily accessible from Kyoto, Nara, and Osaka. Trains from those cities connect to Koya's cable car train.
In the mountainous central area of Wakayama you can find Ryujin (竜神), an area famous across Japan for its hot springs, or onsen. It's a place of wild scenic beauty, especially during the fall when the leaves change color.
South of Ryujin is Hongu, best known for Hongu-taisha, one of the sacred shrines on the Kumano-Kodo. Its newly-built visitor's center has information in English. A riverboat tour down the crystal-clear waters of the river affords views of the old route as well as waterfalls and dramatic rock formations.
On the central west coast of Wakayama, you can find Shirahama (白浜), a white sand beach sought after by visitors from all over Japan. Besides the beach, Shirahama is known for having some of the best onesen, or hot springs, in all of Japan.
At the very southern tip of Wakayama is Kushimoto (串本). This is the southernmost point of Honshu, Japan's main island. There is a Marine Park, excellent for snorkeling and diving.
Nachi-katsuura, just to the northeast of Kushimoto, is home to Japan's tallest waterfall: Nachi Falls. Adjascent to the falls is a temple complex. One climbs to the top of a small hill from the base of the waterfall. It's worth it just for the view of the waterfall with temple buildings in the foreground. Nachi-katsuura is, as the rest of Wakayama, rich in natural hot springs.
Wakayama is particularly rich in temples and history, as is all of the Kansai region. It's not as famous as its neighbors Nara and Kyoto, but if you want to beat the crowds, you are sure to have a real Japan experience.
Stay overnight at a temple on Mount Koya. Koya-san is known to every Japanese person and a top destination for domestic tourism, yet is overlooked by foreign tourists who stick only to Osaka and Kyoto. Their loss is your gain, because Koyasan is truly one of Japan's greatest treasures. For a reasonable rate, you can stay at one of the dozens of Buddhist temples on this sacred mountain. Rates, which include a traditional vegetarian temple dinner and breakfast, run about 9,000 yen per person. You can make arrangements through the English-language website of the Koyasan Tourist Association . No matter your religion, or lack thereof, you can witness and try parts of Buddhist ritual practice for yourself if you desire. Otherwise, the beauty and tranquility of this place will definitely be the highlight of your trip to Wakayama and possibly all of Japan.
Hike the Kumano-Kodo Pilgrimage Route This ancient sacred pilgrimmage route connects many holy sites across several prefectures, but it is historically begun and ended at Mount Koya. The route runs through central Wakayama (through Hongu) and over to Nachi-katsuura before continuing north to Mie prefecture. 
Snorkel/scuba dive The northernmost coral reefs in the world exist here because of the warm waters of the Kuroshio current, which carries warm water and nutrients from the south. Not a diver or snorkeler? Check out the small, but fun Kushimoto Marine Park Aquarium in Kushimoto. 
Soak in an Onsen in Ryujin, Nachi-katsuura or Shirahama Trying an onsen, or hot spring bath, is a rewarding experience for visitors. There are even a few mixed-gender onsen where bathing suits can be worn (only where expressly noted) if the traditional way of getting nude is unappealing to you. (The nude baths are separated by gender.) Of the hundreds of onsen throughout Wakayama, from tiny single pool baths to Hongu's Kawayu where, in the winter, a sennin bath is built directly next to the river, named because it is said to fit 1,000 people (sennin,千人)!
Wakayama specialises in Mikan (oranges) and various other regionally-known products. There is a small gift shop adjacent to Wakayama castle, but little else. Wakayama has one main department store, Kintetsu, which is relatively expensive. Other than that, the best place to do any shopping is in Burakuricho, which has a DonKehote shop.
There are some atmospheric izakayas here but nothing special. Arochi has the token seedy area, which has a lot of hostess bars and other expensive vices.
There are a few small hotels in Wakayama, none of which are really used to dealing with tourists. The most easy to spot is the monstrous Daiwa Roynet, which towers above the city near Wakayama Castle. Nearby, in Burakuricho, there is a new business hotel, and there is the Granvia hotel, a rather exclusive and expensive hotel near JR station.
Perhaps one of the best features of Wakayama is that it is well connected, and provides good access to Osaka, Kyoto, Nara and so on without being on top of them. Wakayama is a smaller city which seemingly makes little effort to embrace tourism, so is a good example of a "normal" Japanese place untouched by the demons of tourism.
The South of Wakayama prefecture is one of Japan's playgrounds, and its well known resort of Shirahama is busy during the summer season. Mount Koya, the atmospheric and picturesque mountain an hour from Wakayama, is a little-known (by tourists) gem.