According to what we can remember about Druids, they considered clover to be magical, and therefore, rare 4 leaf clovers to be even more so. They were also thought to be markers of fairy gardens.
Because Christianity borrowed a lot of traditions from other religions, the clover stuff found a new home in the Christian mythos. St Patrick was said to use the 3 leafs of the clover to teach about the holy trinity. A four leaf clover looks an awful lot like a cross, and therefore would be extra holy.