1)

a) The Shulchan Aruch (Orach Chayim, Hilchos Pesach 451:8) writes, "Wooden vessels, stone vessels, and metal vessels may all be kashered by Hag'alah." The source for this is cited as the Rif in Maseches Pesachim (beginning of page 8b of the pages of the Rif). We note that the Halachah that Hag'alah works for wood or stone does not seem to be stated explicitly in the Gemara. The Rif, who lived after the Ge'onim but before the Rambam, seems to be the first to mention this.

b) This is 3 lines from the top of 8b of the pages of the Rif. He writes:

"Grasp this rule in your hands: Wooden vessels, iron vessels, and other kinds of metal and 'Gormi d'Glali' which have been used with Chametz all year round in a Kli Rishon, must undergo Hag'alah in a Kli Rishon." The commentary ascribed to Rashi, printed on the side of the Rif, writes that "Gormi d'Glali" means utensils made of marble.

So the Rif rules that Hag'alah is effective for wooden and marble utensils but he does not tell us his source.

c) The Ran (DH Nekot) writes that stone vessels have the same Din as metal vessels, and are not like earthenware vessels (for which Hag'alah is not effective). He cites proof for this from the Mishnah in Avodah Zarah 74b, that if the stone tub of a winepress has been tarred by a Nochri it is sufficient to dry it. The end of the Mishnah states that if the tub is made of earthenware, even if one peels off the pitch it remains forbidden.

This proves that stone vessels are different to earthenware vessels. Kashering does not work for the latter but it does work for the former.

2) Above, I cited sources from Rishonim and the Gemara that Hag'alah works for wood and stone. However, I did not answer the question, how did the Chachamim know this?

An answer can be found in Pesachim 30b which states that we see that the outer walls of earthenware vessels give off moisture, so this shows that they absorb, hence they are forbidden. They cannot be kashered because the Torah teaches that absorptions never leave the walls of earthenware vessels.

Rashi (DH d'mid'Aisi) cites Vayikra 15:12, "And the earthenware vessel, which he who had the issue touched, shall be broken, and every vessel of wood shall be rinsed in water." Vayikra 6:21 states, "But the earthenware vessel that it is cooked in shall be broken and if it was cooked in a copper vessel it shall be scoured and rinsed in water." In addition, Bamidbar 31:22 lists metal vessels, about which 31:23 states, "You shall pass it through the fire and it becomes pure."

So the Torah does speak about wood utensils and says that they can be kashered while earthenware vessels must be broken.

3) Wood utensils absorb more easily than stone utensils:

a) In the previous answer I cited Rashi to Pesachim 30b who writes that metal and wooden utensils can be kashered, but Rashi does not mention stone utensils. However, it is easy to prove that stone can be kashered, since this is a Kal va'Chomer from wooden utensils because wood is a softer material than stone and absorbs more easily whatever is cooked in it. Since we see that Hag'alah works for wooden Kelim, which means that the Chametz or forbidden substances can come out even though a lot was absorbed, then certainly it works for stone utensils which absorbed less in the first place.

That is a very logical argument and possibly does not require a proof, but at any rate there is a source for this in the Rishonim. This is based on the Mishnah in Avodah Zarah 74b that we mentioned above. The first part of the Mishnah states that it is sufficient to dry out the stone tub of a winepress. Everyone agrees with this. Then, the next part of the Mishnah cites a dispute concerning the wooden tub. Rebbi says it has the same Halachah as the stone tub, but the Chachamim say that it requires a stronger form of kashering, namely that the pitch must be peeled off. The Rashba writes that the reason why the Chachamim are more stringent for a wooden tub than for a stone tub is that the nature of wood is that it absorbs more easily.

b) To highlight the difference between stone and other materials, we can return to the Ran (Pesachim 8b of the pages of the Rif, DH Nekot) that I cited above. At the end of the paragraph, the Ran writes that they said in the name of Rebbi Yitzchak that stone utensils do not require any kashering at all. Rebbi Yitzchak found a support for this in the Tosefta.

So according to Rebbi Yitzchak, stone Kelim do not absorb anything cooked in them, so they do not need any Hechser. It seems that the Tosefta that he found is the one cited by the Mordechai, Pescahim #585, in the name of the Tosefta, chapter 7 of Zevachim, "stone utensils do not require Merikah and Shetifah (scouring and rinsing) but only Hadachah." The word "Hadachah" usually means "washing," which seems to be the source of Rebbi Yitzchak that stone vessels do not require Hag'alah, but the Mordechai writes that here the word "Hadachah" means Hag'alah. So according to Rebbi Yitzchak, stone Kelim do not require Hag'alah, while according to the Mordechai they do.

At any rate, we learn that according to Rebbi Yitzchak stone utensils absorb less than other kinds of utensils so it is easier to understand why, according to other Mefarshim, Hag'alah is at least effective for stone.

4) This discussion appears to have started in the time of the Ge'onim:

a) At the beginning of my answer to this question I wrote that the Rif seems to be the first to discuss it. I have now found that the Ge'onim, who lived before the Rif, did discuss it, and there are stringent opinions among the Ge'onim that stone utensils are equivalent to earthenware utensils and cannot be kashered. The Tur in Yoreh De'ah, near the beginning of #121, writes, "In a responsum of Rav Hai Ga'on it is stated that stone Kelim are like earthenware Kelim and are not permitted by Hag'alah." I have looked up the Ge'onic literature and see that stringent opinions are given on this matter, but I did not find anyone who explains why. I want to suggest that Rav Hai Ga'on understands that since Bamidbar 31:22 mentions only metal vessels and 31:23 states that if they were used (by the Midianites) with fire, they must be passed through fire to become Tahor, this shows that it is only possible to kasher metal vessels, not any other kind. Even though we see that Vayikra 15:12 mentions wooden vessels, however this does not refer to a vessel that was used with hot food.

b) After citing Rav Hai Ga'on, the Tur continues, "but Rav Alfas (the Rif) gave stone utensils the same Din as Kli Shetef, and this is the main opinion."

Rashi in Chulin (25a, DH Kli Shetef) writes that all vessels which are not earthenware are called Kli Shetef because they can be purified in the Mikveh.

(The word "Shetef" means rinsing, which is why a vessel that can be immersed in the Mikveh is called a "Kli Shetef.")

So the Rif rules that stone vessels can be kashered, and the Tur decided that the Halachah follows the Rif. It is interesting that the Rif changed the practice that seemed to have been prevalent up to his time, that one could not kasher stone utensils.

I found that Chacham Bentzion Abba Shaul zt'l explains the source of Rif. This is in Or l'Tziyon, Teshuvos, vol. 3, chapter 10, section 13, page 127. He is discussing whether plastic plates etc. can be kashered for Pesach, and is lenient mainly based on his understanding of the Rif. He notes that the Rambam, Rosh, Tur, and Shulchan Aruch follow the opinion of the Rif. In DH v'Nir'eh, Chacham Bentzion writes that the Rif's source is Pesachim 30b, that we saw above, which states, "The Torah testifies that earthenware utensils never emit the aborbed forbidden food." He writes that the Rif learns from this that it is only earthenware vessels that cannot be kashered, but all other utensils can be kashered.

5) We learn Dinim of Hag'alah from the Dinim about which vessel is Tahor and which is Tamei:

There is a surprising addition to be made here. I first saw this idea in the continuation of the words of Ran to Pesachim 8b (DH Nekot) that I cited above. After citing the Mishnah in Avodah Zarah 74b, that stone does not absorb forbidden wine while earthenware does, the Ran proceeds to write that we have learned in a Mishnah also that wooden utensils are similar to metal utensils. This is the Mishnah in Kelim 5:11 (the source "5:5" which is written in our texts of the Ran is a printing error), whch states, "A stone oven and a metal oven are Tahor, but a metal oven is Tamei in the same way that any other metal vessels become Tamei." (The Bartenura explains that a stone oven is totally Tahor, and the Tiferet Yisrael #84 writes that the stone oven is the same as all other stone vessels which never become Tamei.)

The Ran concludes from this Mishnah, "One sees that stone utensils are similar to metal utensils and are not like earthenware vessels and therefore Hag'alah is sufficient for them."

The surprising thing is that the Ran learns Halachos of Hag'alah (such as removing forbidden substances absorbed in the utensil) from the Halachos of removing spiritual impurity, Tum'ah, from utensils.

Also, it is somewhat puzzling what the Ran saw in the Mishnah in Kelim 5:11, since a stone oven is obviously Tahor, because all stone vessels are always Tahor, as the Tiferet Yisrael writes. However, I have seen this explained very simply: the Ran observed from the fact that the Mishnah in Kelim 5:11 puts metal and stone next to each other that they are similar to each other, both for Halachos of Taharah and for Hag'alah.

The Vilna Gaon writes in Bi'ur ha'Gra (Shulchan Aruch, Orach Chayim 451:8, where the Halachah of the Rif and Ran is cited that Hag'alah works for stone and wood utensils) that "Yalfinan Isur mi'Tum'ah" -- we learn Halachos about what is permitted and forbidden from the Halachos of what is Tahor and Tamei.

This requires a lot of further explanation.

6) To conclude this topic, I want to try to suggest a few ideas about the comparison between Isur and Tum'ah.

a) The Vilna Gaon that I cited above gives a source for the similarity from Avodah Zarah 75a which states, "In the same way that they said one should do for Taharos, so did they say that one should do concerning forbidden wine." The discussion is about somebody who made wine when he was Tamei and now wants to purify the wine equipment. If he wishes to do this quickly, he can leave the utensils underneath a flowing pipe or a gushing fountain for 12 hours. The same Halachah applies if an Akum has used the wine equipment and one now wants to kasher the equipment to prepare Kosher wine. One does the same thing: he places the utensils under the flowing pipe or gushing fountain for 12 hours. We learn from this that we can compare the Halachos of Tum'ah with the Halachos of Kashrus. Tum'ah is removed from a Kli in the same way that absorbed forbidden foods are removed.

(There is another Gemara in Yevamos, end of 103b, which states that one cannot learn Halachos about forbidden foods from Tum'ah. This seems to contradict Avodah Zarah 75a. It is beyond our scope, at the present moment, to discuss this, but it is mentioned by the Teshuvos ha'Ra'avan #10, cited by the Vilna Gaon.)

b) I found in Sefer Divrei Avraham (Rav Avraham Tcharak, 1870-1942) on Vayikra 11:35 (DH Yutataz) that he writes that in the same way that one cannot do Hag'alah on an earthenware vessel, because the Isur has been swallowed up from one side to the other side. Similarly, the Tum'ah is embedded throughout the earthenware vessel and cannot be removed.

c) So the Rif and Shulchan Aruch maintain that since Tum'ah cannot become embedded in wooden or stone vessels, and they are always Tahor, so, too, any forbidden items which enter wood or stone vessels can always be removed by Hag'alah.

Chazak u'Baruch,

Dovid Bloom