Eastern Mongolia is a region in Mongolia.
While relatively close to the capital, Ulaanbaatar, most of the region isn't yet connected to the center of the country by paved roads. As of 2013, paved roads ends just past Ondorkhaan. Though, there are still plenty of options for buses to the provincial capitals and daily flights to Choibalsan from UB and Hailar, Inner Mongolia. Airports in Ondorkhaan and Baruun-Urt no longer have scheduled flights to UB. There is a rail line from Choibalsan to Russia, but it has no passenger service.
Getting to a province in Mongolia from the capital is much easier than going between provinces. The best strategy is starting as far from UB as you wish to go, say Choibalsan, and working your way back to Ulaanbaatar. There are shared jeeps between provincial capitals and from the cities to the countryside.