<p>What's the story behind our massive repitition of <code>./foo</code> and <code>cd ..</code>. Where do these two <code>.</code> and <code>..</code> come from? Where could they be seen as a way of navigating a file system tree for the first time?</p>

I'm sorry I can't answer properly, but I can recommend these links:
The Evolution of the Unix Time-sharing System
and
A Brief history of the BSD Fast File System
for some interesting historical notes on early file systems and their use.
Other than that, the earliest reference I've found is the 1974 paper "
The UNIX Time-Sharing System
" by Dennis Ritchie and Ken Thompson. The precursor of UNIX, Multics, also had hierarchical file systems and the notion of relative paths, but according to "
Introduction to MULTICS
" it used another notation for that.