Yalkut Shimoni explains that there was a fury debate between the trees and that a specific tree was chosen that was fifty cubits high, so that everyone could see the tree from afar. The Yalkut Shimoni here mentions the cedar tree also.
According to the Midrash in Esther Rabbah (source still seeking, chapter 9), the thorn-tree was used for the gallows.
There are also sources that say that the wood was from the tree of knowledge (see: Haman's tree by Rabbi Heschel Greenberg)
The Yalkut Shimoni writes that the wood, used for the gallows, was originally from the Ark of Noah.
ונטל נסר א' מתבתו של נח שעשה הקב"ה זכרון לעולם שידעו דורות עולם שהביא מבול לעולם שכן כתיב זכר עשה לנפלאותיו וכן כשנהפכו סדום ועמורה כתיב ותבט אשתו מאחריו ועד עכשיו היא עומדת נציב מלח. למה זכר עשה לנפלאותיו שיהיו הדורות מתנין שבחו של הקב"ה
If we look back to the point where G-d instructs Noah to build the ark, G-d instructs Noah to build it from Gopher wood:
Make yourself an ark of gopher wood; make it an ark with compartments,
and cover it inside and out with pitch.
The Onkelos says that gopher wood can also read as cedar wood דְּאָעִין דְּקַדְרוֹס:
Make for yourself an ark of cedar wood. Make the ark into compartments and caulk the inside and outside with tar.
See also the Radak (ad loc.).
According to the Rabbeinu Bahya, it was light-weight kind of wood
and well-known to the people.
So, you ask what kind of wood it was. Well, if we build unto the words of the Yalkut Shimoni, it was the same wood as the Ark of Noah's was. Therefore, according to Onkelos, it was cedar wood. According to the posuk itself, it was gopher wood.