This was basically asked to Hillel by the convert who was only willing to accept the written law. Hillel showed him, that anyone reading the Torah needs to rely on a teacher to tell them that a certain word means what it means, and so clearly there must have been a tradition of interpretation. (Shabbos 31a) That very self-same tradition, it so happens to be, not only includes translations/interpretation, but additions (halakha lemoshe misinai) as well. Once we are forced to accept one aspect of that tradition, we need to accept the rest as well.
When it comes to specific laws - it wouldn't be possible to have a written record, because these matters were prohibited to be written (Temurah 14b), and therefore we're going to have to take them on faith. There's no other way for there to be any evidence. (For example, even if you dug up tefillin from every generation since Moshe, and they were all black, I could tell you that that was merely because it was the easiest color ink to make, or traditional, but not because it was told to Moshe by God at Sinai- we have no audio recordings from that particular event).