The red wanderer is one of the seven wanderers visible in the sky over the known world. Colored red, it is associated with the Smith, one of the gods associated with the Faith of the Seven.
Among the free folk, the red wanderer is known as the Thief. Supposedly when the Thief is visible within the constellation of the Moonmaid, it is a good time for a man to steal a woman.
Ygritte tells Jon Snow that the Thief was bright in the Moonmaid the night he captured her.