From one of the explanations of eating milky foods on Shavuos, we understand that it was not possible to do all the mitzvos connecting with preparing meat for food immediately after accepting the Torah.
Shechting an animal and skinning it are also stages in preparing tefillin. So do we have any sources that tell us how long after the Torah was given did the Jewish people start wearing tefillin?
As specified in Shulchan Aruch, OC 32:12, t'filin can be made from an animal that died by any means, not just via kosher slaughter, so there would be no need for the Jews to wait for kosher-slaughtered animals after they got the Torah.
(This doesn't preclude their waiting for other reasons, which other answers may yet explore.)
A tip of the hat to Double AA for this answer. He posted it as a comment on the question, but it really is an answer. He's not posting it as such for whatever reason, so I'm doing so. But I'm posting it as a "community wiki" answer so I don't get the reputation points from it.
Nezer HaTorah - Rabbi Reuvain Ravonisky mentions the Mechilta Parshas Beshalach 14 which according to him seems to indicate that the Jews wore Tefilin from the time they left Egypt.
He also mentions in the name of the Maharil Diskin (menyioned in Siddur Otzar HaTefilos) that when we say "Hoshana Yekorcha Imom Maavirin" this is proof that the Jews wore Tefilin out of Egypt.
He has a discussion from the Rashba how it was possible to have Tefilin with the 4 Parshios when they have not yet heard Shema and Vehoyo Im Shomoya. In addition there is a discussion as to how they were wearing Tefilin and it was Yom Tov? Please see the above link for further explanation.
