You can remember the meaning of 证据 with this easy mnemonic:
This piece of evidence is proof (证) that what you said is in accordance to (据) what really happened.
Using mnemonics to remember the meaning of Chinese characters like can have an enormous impact on how long to learn Mandarin it takes.