This is not a Gold Bug, and you don't have to solve any puzzles, but it's an Edgar Allen Poe Story in which two friends and a servant go on a hunt for the fabled buried treasure of Captain Kidd. Through a character named William Legrand, Poe explains how to decode an encrypted message.
Vs gur pbbeqvangrf ner rkpryyrag, lbh jvyy frr gur fhfcvpvbhf cvyr sebz gur genvy. Vs gurl ner abg, V'ir cebivqrq n fcbvyre cvpgher.