The question about where did the Jews get tekellet in the desert could be asked about any number of items such as where did the Jews get:
a) the four species
b) wheat for matzah, showbread, menachot etc
c) oil for the menorah
d) wood to burn on the altar
e) wine for the korbonot
The most prominent answer seems to be as mentioned by Baruch Sterman that they acquired these supplies from non-Jewish merchants who visited them in the desert. There seems to be a Yerushalmi (Challah perek bet) to this effect regarding the wheat for matzot, and a Ramban who says this about etrog.
Other sources:
Shir Hashirim Rabah Parshah 4
[
www.din.org.il]
[
www.tshuvos.com]
Tzvi Daum
[
torahskills.org]
[
twitter.com]
