How Did Gimli Know?
 

At the very end of Appendix A there's a dwarf family tree that was compiled for King Elessar by Gimli. No problem with that, except that Gimli himself is in the family tree, with two dates under it. The second date, according to Appendix B, is the date that Legolas and Gimli sail their grey ship to the Undying Lands. Gimli could not have written the second date on the family tree. Was that a later addition to the Red Book by one of Master Samwise's descendants?

I'd probably say it would have to be or it's just something Tolkien overlooked.

Gimli the Seer?
 

Gimli did not have the foresight to predict the year of his passing into the West with Legolas. Legolas decided to leave Middle-earth after the death of King Elessar, so there was not a set date for their departure that Gimli could have written in the genealogy either. Thus we are left to conclude that it was someone else who added the date of Legolas and Gimli's departure to the family tree.

Adding to the record
 

The idea that this event was added to the Red Book of Westmarch at a later date is entirely consistent with Tolkien's mythical history of The Lord of the Rings as a translation of a Fourth-Age document. Ancient documents often contain additions by later generations, particularly historical chronicles. I would guess that one of the Fairbairns is supposed to have inserted the date for the sake of completeness after Gimli and Legolas had made their departure.

Quite true, Squatter. In fact, the family tree is immediately followed by a written third-person account of the departure of Legolas and Gimli, titled Here follows one of the last notes in the Red Book.

Thanks for your reply, Squatter. That clears things up for me. I just was quite flummoxed ( :D ) when I noticed that while reading the appendices.