Secretary of the Interior in 1881 was Samuel J. Kirkwood. He was an Abolitionist, Republican Senator in the Iowa State Senate, Governor of Iowa during the (un)Civil War, and served as Secretary of State under Presidents Garfield, and Arthur from 1881 to 1882. In 1860, while he was governor, one of John Brown's raiders, John Coppeck escaped to Iowa after the raid. Kirkwood refused to honor extradition papers and allowed Coppeck to escape, causing a national scandal. He left the Governors Office in 1864. From 1865 to 1867, he served in the US Senate, and again from 1877 to 1881. In-between time, he was once again elected Governor of Iowa. In 1881, he was appointed Secretary of the Interior. Not much is known of him personally, but indirect sources seem to indicate that he was fond of fly fishing. Could it be he?
Are you sure it wasn't 1891? Because, with the exception of the upper Yellowstone River Drainage, all of the rivers and lakes above major falls in the Yellowstone National Park were virtually devoid of any game fish prior to government stocking programs, which began in 1889.
There is evidence that Paleo Native Americans of the Clovis culture were making fish hooks in the region as far back as 11,000 years ago. It doesn't take a big stretch of the imagination to figure that at some point, someone would've gotten the idea to tie a few feathers, or fur to a hook to imitate an insect.
In 1817, John Coulter recounted his adventures in the Yellowstone area to British writer William Bradbury. During the winter of 1807-1808, Coulter described his experiences of catching fish in the upper Yellowstone by what passed for angling in those days. Bradbury published Coulter's memoirs as a footnote in his 1819 book, "Travels in the Interior of America. However, since this was before Hardy's patent for the fly reel in 1888, you may not consider this fly fishing, but the 1881 expedition wouldn't qualify under those conditions either.
I'd put my money on a Clovis fisherman with a fly and a club. Somewhere there is probably an undiscovered cave-painting depicting just such an event........