Puno's elevation is about 3,822m (12,565 feet), which means it is fairly cold, especially at night. If you arrive from a lower elevation, you might want to spend a day or two taking it easy in order to acclimatize.
Trains to and from Cuzco travel only 3 times per week. Other trains travel down to Arequipa. The rail trip from Puno to Cuzco, which is run jointly by Peru Rail and Orient Express is spectacular, one of the world's great train journeys.
The trip takes in Andean mountains and valleys of the Huatanay River, before reaching the Andean Plains, La Raya (the highest point of the route) and finally Cuzco. Without a doubt, the best way of travelling to Cuzco and Macchu Picchu.
Daily buses depart to and from Cuzco and Arequipa. The ride form Puno to Cuzco takes around 8 hours. There's a night bus leaving Puno at 19h30 and arriving in Cusco at 4h30 am.
Daily buses depart to and from La Paz, Bolivia on two slightly different routes.
You should change some money at the border in order to be able to pay the ferry in Bolivianos. Be prepared to change buses in Copacabana. This will mean you will lose your good seats.
When the overnight bus to Cusco stops at the state line for the police to inspect cargo underneath the bus, get out and watch your backpack. My mp3 player was stolen in this way.
Taxis or motor-rickshaws will not charge you more than 2 S/. for a ride within the city.
Urban colectivos charge 0,50 S/.
Most Puno sights are actually not in the city itself. Check the "Get Out"-section below.
Visit the Church of San Pedro.
The Sistine Chapel of the Americas.
La Raya Ranch.
You can buy souvenirs here for less than in Cuzco or Lima. There is a fairly large market down by the water.
In and around the mercado central are several budget places to lunch for less then 3 Soles.
Down Jr Tacna from the mercado many restaurants have dinner menus for 3 Soles or so.
Most touristspots are in and around Calle Lima, with main courses around 20 Soles. A little bit of bargaining will get you a discount, but don't push it too far if you want your food prepared without any bodily fluids.
Cafe restaurant Monterrey, Pasaje Grau 158, has reasonably cheap and good breakfasts.
Restaurant pizzeria Ollantay, Pasaje Grau 160, has pizzas, trout and alpaca. Ask for el menú.
Restaurant Vida Natural, Jr. Lambayeque 141. Perfect if you like natural, fresh and tasty vegetarian food. Breakfast, lunch and dinner. Cheap complete menus. Custom dishes on request. Friendly owners. (Closed on Saturdays)
Fruitjuices at one of the many juguerias on the second floor of the market.
Many gringo spots at or near the pedestrian mall.
Hostal Los Uros, Theodóro Valcárcel N8 135, 051-352141. Clean and decent hotel close to the center. Popular with foreigners. A single with shared bathroom cost 20 soles. Ask for a discount in low-season.
Hostal Lost Pinos Inn Tarapacá 182. Helpful staff, breakfast, private bathrooms, affordable. 
Sonesta Posadas del Inca Lake Titicaca Sesquicentenario 610. Only 5 kilometers from Puno's Main Square, the Sonesta on Lake Titicaca offers easy access to all tourist activities and attractions, including the fascinating floating reed islands of the Uros people, Taquile Island and the Chullpas of Sillustani.
Titilaka A modern luxury refuge located on the shores of the Peruvian side of Lake Titicaca, featuring 18 lake-view Suites and providing guests with a richly authentic experience in the region. Phone: +51 1 7005100
There are loads of agencies offering trips from here, and most hotels and inns will be more than happy to reserve for you. Note that the latter often charge an extra 5 S/. for this service.
Walking up in the hills gives nice views over the city and the lakes,
but it is dangerous! Tourists are often the victims of armed robberies in the hills.
Chucuito (19km, 1 Sol by colectivo) can be done as a daytrip from Puno, -or en route to Bolivia.
Cutimbo is a nice daytrip, -for pre-Inca ruins and views.
Sillustani has the best examples of pre-Inca tombs in the area, -and also has some nice lakeside views.
Isla Taquile, famed for its traditional Titicacan way of living, can be done either as a daytrip, or staying a night or two.
This is a usable article. It has information for getting in as well as some complete entries for restaurants and hotels. An adventurous person could use this article, but please plunge forward and help it grow!