All international flights to Tehran land at the new Imam Khomeini International Airport  based 37 km southwest of Tehran. Pilgrimage flights to Saudi Arabia still fly from Mehrabad airport. There are 70 smaller regional airports, for example those in Shiraz, Mashhad, and Isfahan, and these have daily flights to many international destinations.
Dubai has scheduled flights to many Iranian cities, including Tehran, Shiraz, Isfahan, Kerman, Lar, Mashhad, Tabriz, Kish Island, Bandar Abbas, Bushher, Zahedan, Kermanshah, Chah Bahar and is therefore worth considering travelling to Iran from. Flights are operated by Iran Air, Emirates (for Tehran), Iran Aseman Airlines, Mahan Air and other Iranian companies. Fares are relatively cheap on Iranian carriers, ranging from US$100-250 for a return trip depending on your destination and time of booking.
IranAir and MahanAir connect Tehran with some of the major European cities as well as destinations in Asia and Middle East. European companies landing in Tehran include BMI, Lufthansa, KLM, Alitalia, Turkish Airlines, Austrian Airlines, Aeroflot and Middle-Eastern airlines: Saudi Arabian Airlines, Emirates, and Etihad. AirAsia also has flights to/from Kuala Lumpur beginning on August 2010 (suspended as of October 2012). So finding a flight to Iran should not be hard.
Connections are also easily available via Manama, Bahrain using Gulf Air (but has stopped recently). Additionally, Qatar airlines offers several flights to Iran and provides non-stop service to Doha from to many US cities.
Low-cost carriers (LCC) also operate flights to Tehran or other cities in Iran.
Pegasus Airlines has flights to Tehran via Istanbul.
Germania Airline has flights to Tehran via Berlin, Dusseldorf and Hamburg and to Mashhad via Hamburg.
Air Arabia has flights to Tehran and Shiraz via Sharjah.
Jazeera Airways has flights to Mashhad via Kuwait.
Air Asia has flights to Tehran via Kuala Lumpur (suspended as of October 2012).
Shaheen Air has flights from Mashhad to Lahore in Pakistan.
Note that if not staying in Tehran and planning to get to any city other than Tehran upon your arrival, you would have to change airports, from Imam Khomeini to Mehrabad, 40km away, to get to your domestic flight. Allow at least 3-4h between the flights. If going to Mashhad, you may be able to avoid the plane change in Iran using Turkish Airlines, Gulf Air, Kuwait Airways, Jazeera Airways, or Qatar Airways. If going to Shiraz, several flights from Persian Gulf States are available. For Tabriz, you can try travelling via Istanbul on Turkish Airlines or via Baku on IranAir.
In spite of economic sanctions the majority of Iranian based airlines did not have high level of incidents during recent years. However sanctions resulted in inability to purchase new planes and the fleet of all airlines are old. Among Iranian based airlines Iran Air, Mahan Air and Aseman Airlines have been completely safe with no serious incidents during recent years. Due to safety issues flying with other Iranian based airlines is not recommended. The service and flying skill of Iranian pilots are fairly well known.
Due to sanctions there are no direct flights at present from Canada or the USA, but you could travel via either Europe or Persian Gulf States. Non-stop flights from Dubai via JFK, IAD, San Francisco, Los Angeles, Houston or Toronto are good bets. Visitors from Australia or New Zealand can consider travelling via Dubai or Abu Dhabi, or can use a combination of Iran Air and Malaysian Airlines to get from any major city in Australia to Tehran, via Kuala Lumpur. Air Asia also has good deals from Australia and New Zealand to Tehran with a stop in Kuala Lumpur.
There are weekly flights from Sulamaniya in Iraqi Kurdistan to Sanandaj and from Arbil to Urmia.
From Damascus in Syria there are charter flights to Tabriz, Tehran, Yazd, Isfahan, Mashhad. There are agencies in Seyyedeh-Zeinab district (a popular place with Iranian pilgrimages) that can sell you empty seats of these charter flights for less than 100$.
Iran is connected to Pakistan via the following air links:
Iran Air connects Tehran to Karachi
Pakistan International Airlines (PIA) connects Zahedan to Quetta
Shaheen Air a low cost Pakistani Airline connects Mashhad to Lahore.