The source for it is in the Gemara (Shabbos 61a), and it is codified as halachah in Shulchan Aruch (Orach Chaim 2:4).
The basic idea behind this practice is:
We find that the Torah generally privileges right over left - in this week's parsha, for example, a metzora's purification rites include having some of the blood of one of his sacrifices, and some of the oil accompanying it, applied to his right ear, thumb, and big toe (Lev. 14:14-17 and :25-28). Furthermore, the various mitzvos that involve handling something (such as taking the lulav) are done with the right hand.
On the other hand (sorry!), when it comes to tying the tefillin, the left is privileged over the right.
So to accommodate both preferences, we start with the right side when it comes to putting on items of clothing (it's not only shoes - Mishnah Berurah 2:4; it also applies when bathing - ibid. 2:7), and with the left when it comes to tying.