He reconstructed the wall with bricks (that) people had given her before, but (that) she had refused to fit together.
Do I need the "that"'s? Why or why not?
Yes, I would use the "that"s. However, this is a question of what can be left out -- which is not governed by hard and fast rules.
The first "that": Definitely use it, because otherwise the reader is going to trip over the words "bricks people." It can sound odd when quickly reading, someone built a wall with "bricks people," like "lego blocks." This is an example of using "that" to separate words so they don't sound like an odd phrase.
In the second case, "that" is also helpful. Here are suggestions:
"He reconstructed the wall with bricks that people had given her before, but that she had refused to use."
Or
"He reconstructed the wall with bricks that she had been given but refused to use."
I'll disagree as a (fellow) native speaker with user8356's answer. Personally my choice would be to omit the first "that" but include the second.
You would be widely understood with any combination or omission, but I always find that sentences flow better with variation, and "but that" (or "but which") to me better directs a followup comment towards something you've just mentioned.
He reconstructed the wall with bricks people had given her before, but that she had refused to fit together.
Hmm i thik that putting ''that'' or not putting it is correct. You can say this : ''He reconstructed the wall with bricks that people had given her before, but she had refused to fit together.''