There is a mid-sized airport in Gondar. Ethiopian airlines has daily flights to the city - usually leaving Addis around 0700. Flights are also available to/from Axum, Lalibela, and Bahir Dar. Ethiopian Airlines flights are frequently cancelled or rescheduled at short notice, so allow plenty of time if travelling for an international connection.
A number of options are available. Prices start at 20 Birr for very basic rooms.
Many travellers go to Gondar to visit the Simien Mountains, about a 3 hour bus ride north of the city. Treks in the mountains can be arranged in Gondar, and you will be approached by many touts offering a wide variety of treks. The advantage of using their services is they may be able to put you in a group of other travellers, which will cut costs, and they can arrange for private transportation to and from the park. They can also arrange to drive you to a campsite and pick you up from another, which is useful if you are short of time.
It is also straightforward to arrange everything yourself, and definitely cheaper if you aren't splitting the costs with anyone. Debark is the staging point for all treks in the Simien Mountains and can be reached by bus from Gondar. On arrival in Debark, go to the park office in the south end of town (which you will pass on your way in). They will arrange for permits and the mandatory scout, and can find an official guide, cook, mules, and a muleman if desired. They also have gear for rent, although it is low quality stuff.
Unfortunately, a lot of people will hassle you in Debark. If you are planning to hire a guide, make that one of your first tasks when you arrive since your guide will get rid of unwanted people following you around and can help you sort out any last minute details or concerns. Do not hire an unofficial guide off the street -- travellers frequently complain about their experience with unofficial guides!
There is food suitable for trekking available in Debark, but it is cheaper to buy it in advance in Gondar where there is a much better selection. The scout, guide, and muleman will likely expect you to feed them, so bring along extra.
The best hotel in Debark is the Simien Park Hotel, south of the bus station. There are a few other decent places nearby if the Simien Park Hotel is full.
There is a road running from Debark into the park and several trucks run down it each day, but tourists are prohibited from using them. As a tourist, the only way into the park is to hire a 4WD or walk. Although shorter treks are possible, a 5-day trek from Debark to Sankabar Camp to Geech Camp to Chenek Camp and back to Debark via Sankabar (skipping Geech) is about as short as you can get without missing some of the main sights. You need 9 days to trek to Ras Dashen, the highest peak in Ethiopia, and back without transport.
Well organised, if expensive, trips to the Simien Mountains can be arranged in Gondar through Seyoum at Explore Abbysinia Travel. His office is underneath the Circle Hotel, facing away from the main road. He can also organise very good value guided tours of Gondar, which is worth doing as a guide is effective at warding off unofficial guides and other hassles.
Daytrips to the Simien Mountains from Gondar can also be arranged, but you won't have time to do much other than step out of your 4WD for a few minutes to snap some pictures.