Tellers of tall tales blame the fear on the Knights Templar, or maybe just on King Philip IV. The order was famously arrested all across France on Friday, October 13, 1307. The story of this genesis of the superstition was trotted out as factual in Dan Brown's The Da Vinci Code.
Fears of the date Friday the 13th don't really appear anywhere in print much before 1907. In fact, the phobia may have been popularized by the 1907 novel Friday, the Thirteenth by Thomas W. Lawson, about a creepy stockbroker who engineers a panic on Wall Street on a Friday the 13th by playing on superstitious fears of the number 13.
For everything you ever wanted to know about Friday the 13th, read Nathaniel Lachenmeyer's book, Thirteen : the story of the world's most popular superstition.
Several readers wrote to insist that the proper term for fear of Friday the 13th is paraskevidekatriaphobia.
Paraskevidekatriaphobia was a recent term created in the 1990s by Therapist Dr. Donald Dossey for fear of Friday the 13th. The older term is friggatriskaidekaphobia. Friday is Frigga's day. Frigga was an ancient Scandinavian fertility goddess, analagous to Venus, who was worshipped on the 6th day of the week (so I suppose people have gotten frisky on Fridays for a very long time). Frigga was pegged as a witch by early Christians, and so the 6th day of the week was referred to as the witches' sabbath.
Triskaidekaphobia is the fear of the number 13. Friggatriskaidekaphobia combines frigga with triskaidekaphobia, and first appeared in 1911.
Mass murderers Charles Manson, Jeffrey Dahmer, Theodore Bundy all have 13 letters in them, in case you are the kind that worries about such things. And if you are the sort who is really concerned about it, stay away from Sacramento, California, as it contains a street corner at the convergence of 13th Street and 13th Avenue.