I've heard a few times that in the times of Moshiach the Halacha will follow the opinion of Beis Shammai. What is the source and reasoning for this? Is it true? We will no longer follow Beis Hillel but follow Beis Shammai?
The idea that the Halacha will be in accordance with Beis Shamai in the time of Moshiach comes from the Arizal. It is quoted in his name by Mikdash Melech to Zohar Parshas Bereishis 17b and in Likkutey Torah (Rabbi Shnuer Zalman of Liadi) Parshas Korach 54c. The Arizal interprets the Mishna in Pirkey Avos (5:19) that an argument for the sake of heaven such as that of Hillel and Shamai will endure; although now the Halacha is like Beis Hillel, the argument will endure as later the Halacha will be like Beis Shamai. An alternate source is Tosfos Chadashim at the beginning of Avos who brings this in the name of the Gaon of Nikolsburg.
There are two general explanations brought:
1) Mikdash Melech: Hillel represents kindness and Shammai severity (hence the rulings of Beis Hillel are almost always more lenient). When Moshaich comes the advantage of the severity will be revealed and therefore the halacha will be in accordance with Beis Shamai. [Based on this reason some say that this is only in cases where Bais Shamai are stricter].
2) Tosfos Chadashim: Bais Shmai comes from such a high level this present world is incapable of withstanding and only when Moshiach comes will we be able to follow their opinion. [It seems based on this reason we will follow all Beis Shamai's rulings, not only the stricter ones.]
The Lubavitcher Rebbe explains at length in his Kuntres "Torah Chadosha Me'Iti Teztzei" how the fact that the Halacha will change in accordance with Beis Shamai is consistant with the immutable nature of the Torah.
While the Arizal seems to be the earliest source for this concept, as brought by @Michoel, some other sources include (brought by Rav Yehoshua Hartman in his notes to Maharal's Ohr Chadash Chapter 9 fn. 561):
Siddur HaGra (Avnei Eliyahu) in the name of the Gra, commentary to Birkas Yotzer HaMeoros.