The lower cave (the one which used to be open, but got sealed up by a rail line) under the "Ruby Falls Caverns" by Chattanooga supposedly has graffiti as you described, including (supposedly) Andrew Jackson's autograph. :')
That would be cool, a real Andrew Jackson signature.