We start at the very foot of the mountain;
to have a hard time doing sth.
which means that the person in question finds it particularly difficult to do, or get accustomed to the sentence argument that is chosen.
If now we choose the sentence argument to believe,
to have a hard time believing sth.
this simply demonstrates that the person in question ponders the actual truth of something that is given as a statement; leaning on the side of scrutinizing what was being said.
Lastly, topping it of with a negation
I don’t have a hard time believing that anyone could stay mad at you
person X does not find it very hard to believe that any arbitrary person Z could possibly be angry with person Y for an extended period of time. In other words, person X is very positive about the fact that person Y is of such sympathetic nature, that it would lead any person Z to quickly forget about the bad thoughts they had entertained for person Y.
I'd always recommend this train of thought to logically build up a meaning you are looking for (by utilizing a dictionary), until you reach the tip of the ice berg, eventually. A great way to do this is by using the Cambridge Dictionary, which will provide you with basic definitions and sample sentences for the vocabs you seek.