According to the wikipedia entry for Memorial Day, the observances began at the end of the Civil War, but the name wasn't used until 1882:
These observances eventually coalesced around Decoration Day, honoring the Union dead, and the several Confederate Memorial Days. [...]
The alternative name of "Memorial Day" was first used in 1882, but did not become more common until after World War II, and was not declared the official name by Federal law until 1967.
The earliest instance of "Decoration Day" in the NYT archives seems to be from May 19, 1869; but a search for "Memorial Day" turns up this touching article from June 7, 1868, under the headline "An Incident of Memorial Day":
Posted by Mark Liberman at May 28, 2007 02:38 PMThe Layfayette (Ind.) Courier, in its account of the decoration of soldiers' graves in that city on the 30th ult., says a wreath of flowers, accompanied by a note from a little girl about ten years of age was exhibited. The note was addressed to Col. Leaming, Chairman of the Committee of Arrangements, and was as follows:
Col. LEAMING: Will you please put this wreath upon some rebel soldier's grave? My dear papa is buried at Andersonville, and perhaps some little girl will be kind enough to put a few flowers upon his grave. JENNIE VERNON
The reading of the note created a profound impression, the wreath was deposited upon the grave of an unknown rebel soldier -- the only one remaining in the cemetery.