They wanted to leave something behind -- anything however small.
Brooks had been in prison for fifty years. The movie plot shows nothing of having family visit him or communicate with him. When he was paroled, he had only one friend on the outside, Jake the crow who never showed up. He had friends on the inside, but now they were cut off. Greater society shunned him, as the grocery double-bagging scene indicated. So he decided not to stay. He was going to be a man that had been forgotten completely. The only thing he could control was choosing his last day and leaving a mark with a pen knife. Brooks knew nobody would know who he was. He just wanted to leave the world just one tiny bit different.
Red was the same way, and would have probably had the same fate. But he had Andy. And that allowed Red to have his out. He left his mark also, but this time as a sign that this chapter of his life was over and there would be another one to begin.
Within the plot of the movie, the marks were not really about people understanding the who and why of it all. It was only about the fundamental concept of knowing you were here in this life, and left something -- however insignificant -- behind.
Cinematically, the stark contrast between the two marks makes for good, heartfelt drama.