A fuller is the rounded or beveled groove or slot in the flat side of a blade which make the blade lighter -- not as some suggest a blood groove. When did the practice start? I suspect it was a parallel discovery but could be wrong.
In western Europe it seems that the grooves appeared in swords about the eighth century, according to H. R. Davidson's The Sword in Anglo Saxon England as related on this forum post.
In other areas it was probably invented independently. For instance, the Japanese have a long tradition of sword making, including fullers, and likely came up with that on their own.