All big cities in Europe are connected with Stavanger. All the big operators are coming than in Stavanger and the planes are always full.
The main reason is the oil and gas industry and the commuters moving in (and out of) the Capital of Norwegian Oil and Gas.
At the moment there are two airlines operating in Norway., SASBraathens ( http://www.sasbraathens.no/Pages/EN/WebRes/braathens.html )and Norwegian ( http://www.norwegian.no/sw7127.asp ). There are also some direct flights to/from London, Nice, Amsterdam and a few other cities in Europe.
At the moment there is a pricewar between the two airlines in Norway so if you plan ahead you will be able to get some good prices on the tickets :-)
The Airport is about 15 minutes from the city by taxi/bus.
The best way to come here is of course by air. The airport at Sola has connections with London, Copenhagen, Amsterdam and so on. But it is also possible to catch the train here. Stavanger is actually the end of the line.
The best way to get around is by walking because it is not such a big town. But if you need to get around there is a page that describes the timetables for buses, boates and train. The only problem is that it only seems to be in Norwegian. But check it out on http://www.rkt.no/