I know that large region of Eurasia had some indigenous peoples and a few nomadic tribes, but did the early Russians (or any Eastern European civilization for that matter) explore the land east of the Ural Mountains all the way to the coast during or before the Medieval ages?
The exploration and conquest of Siberia was inspired by the success of the robber mercenary Yermak in 1582. He was hired by the Stroganov merchant family to deal with the Sibir Khanate which was harrying their mines. Yermak's campaign was super successful and all his men received a pardon from the Tsar whereas Yermak himself got ennobled and received guns and Russian troops.
Siberia immediately attracted dozens of cossack adventurer bands building forts, exploring, trading and fighting their way to the East. Tobolsk was founded in 1586; Tomsk in 1604; Yakutsk in 1632; By the 1640s they had border skirmishes with China; Khabarovsk was founded in 1658. In 1689 there was the first (border and extradition of criminals) agreement between the Chinese emperor and a European monarch: the treaty of Nerchinsk.
The first recorded Russian crossing of the Bering Strait happened by accident in the 1648. The cossack ataman Semion Dezhniov was trying to sail around Kamchatka but got marooned on the coast of Alaska. Some of his sailors starved to death and they didn't find any signs of civilizations (or food) save for a random basking walrus. They left for good without the faintest idea they have been to America.
A half century later a letter from Leibnitz alerted tsar Peter the Great that America should be right to the east. So he tasked the Dane Vitus Behring with the exploration. Now the strait bears his name.
source: V.K.Andriyevich - Siberian History.
or any Eastern European civilization for that matter
Well, if they did they didn't leave a massage. Mongols, we know for certain, went the other way round. Does it count? The Huns maybe did as well, provided they're the same as the Xiognu of the Chinese chronicles.
What happened before is *pre-*history. No sources there. You'll have to ask the people who are into phrenology, zootheology, theosophy, linguistics and pseudo-archeology.