The story
The Titanic was an ocean liner that sank on the morning of April 15, 1912 after striking an iceberg. The phrase rearranging the deck chairs on the Titanic implies trying to move the chairs on the deck around while the ship is sinking, a pointless activity.
Etymology from Wiktionary, CC BY-SA 4.0.