The region inhabited by Baluchi people spreads from southeastern Iran over Afghanistan into western Pakistan. Local Iranians tell, that outside of Zahedan, the Iranian authorities don't have much grip on the region and thus consider it as not as safe as the rest of Iran. Also, Baluchi locals don't feel well represented by the country's government and don't share Iranian culture and language. Read stay safe for more information.
Zahedan has a domestic airport which is served frequently from major airports inside Iran.
The new train station connects Zahedan with the Teheran - Bam line. The trip from Teheran takes about 25 hours overnight and departs Teheran railway station at 11:20. As the train station is not situated in the city centre you may need a taxi, to get towards Azadi square.
Zahedan is connected by bus with all bigger surrounding cities like Bam, Kerman, Zabol and Mashhad (only twice a day). Alternatively Mashhad can be reached via Zabol, where you can catch one of the more frequent running buses to Mashhad.
Savaris connect Zahedan with Bam, Zabol and cities deeper south in Baluchistan, like Khash and Iranshahr. The huge advantage of going by Savari or even "dar basteh" (lit.: closed door; private car) is that you can tell the driver easily to drop you off or stop anywhere for taking photos. Recommended for Shahr-e Sukhteh on the Zahedan - Zabol road about 55km before Zabol.
I do not recommend taking the bus into deep Baluchistan unless you speak Farsi or the local dialect well. Your presence will raise interest and gain attention. Also you might find yourself in a situation where your local contacts can't be reached as there is rarely network service with Irancell and other providers. This of course does not count for the Zahedan - Zabol road, which is well maintained and about to be upgraded and the connection to Mirjaveh at the Pakistani border.
By far the best way deep into Baluchistan is by car. Either private or hired with driver. Hired in Zahedan he will most likely speak or at least understand the local dialects. Also he might be able to tell you when a situation or location turns dangerous. Still, you might need to argue a lot about your intended stops. Checkpoints are not as common as written in the guidebooks, still there are a few. Focus of military or police officers at checkpoints may reach from your documents to your luggage, as the region is known for drug trafficking. Just remain calm, follow the officers orders and do not overreact or act nervous. Most officers I've met knew enough English to make it easy to understand their demands. Roads in general are not better or worse than anywhere else in Iran. A private taxi for a ~800km trip through southern Baluchistan finishing in Bam which took the entire day cost in end of Feb. 2015 around 3500000 Rials, albeit our driver got very unhappy as he realised he could have asked for more.
Baluchistan is one of Iran`s most violent places. The adjacent Pakistani region of Balochistan is a refuge for Afghan Taliban, Lashkar-e-Jhangvi and other religious extremists. In February 2015 there were only a few police checkpoints, mostly on the N93 from Iranshahr to Bam. Police will probably search your vehicle looking for smuggled goods. After quickly checking your travel documents you may pass on. Officers are usually friendly towards foreigners, but a heavily stamped passport will arise some suspicion. The locals say that the government doesn't have much influence on this remote part of Iran, so you may be confronted with dangerous situations, as this province has a reputation for drug trafficking and petrol smuggling. It's best not to arouse too much attention while travellIng and better to travel fast because a non-Persian / Arabic / Pakistani looking traveller seems like a pink panda to the locals, thus staying overnight outside of Zahedan may quickly spread by word-of-mouth!
There is a connection to Quetta from Zahedan airport.
A train running twice a month connects Zahedan with Quetta in Pakistan. Get a visa before entering Zahedan as it is unlikely you'll be able to get one at the local Pakistani consulate.
Regular buses connect Zahedan with Mirjaveh, where you can cross the Pakistani border towards Taftan. Keep in mind there is a 1,5 hours time difference between Iran and Pakistan.