IIRC, it started during the Civil War. The Union Stamped all military material with "U.S." so everyone would know it was gov't property. Legend was that someone asked what the initials stood for, and someone answered "Uncle Sam." and an American icon was born.
Of course, this is probably just one story. Sort of like how the Willys MB/Ford GPW became the "jeep".