The Chest key is given by Redbeard Frank during the Pirate's Treasure quest. It opens the chest upstairs the Blue Moon Inn to receive the Pirate message. The Blue Moon Inn is located at Varrock.
Directions on how to get there: Go to Varrock square and walk south, across from Thessalia's Fine Clothes in Varrock, You should see a big building that has a Picture of a pint of beer, it is the Blue Moon Inn, Go in there.
In the Inn, go upstairs, and search around for a treasure chest. Use the key on the chest. After opening the chest, the key disappears. You can now continue with the Pirate's Treasure quest.
The update history project is a work-in-progress – not all updates to this topic may be covered below. See here for how to help out!