sahelaziz: Welcome.

"Though the followers of Sathya Sai Baba that I have spoken to do not consider themselves Hindus..."

Not all think that way for one thing. Second, followers of Satya Saibaba are from many religions, including christianity, islam etc.  

"Sathya Sai Baba is the spiritual teacher of his religion, yet there are many accounts of trickery associated with him. In fact, there are many videos on Youtube where you can clearly see that when he is performing his miracles, he is using sleight of hand"

Spiritual teacher may be, but certainly not of "his religion". These kind of people are there in every faith known to mankind. Nothing new. Many follow them, some ignore them and some abuse them. That is the way of the world. One can do nothing about it.

" My question is that once a person who follows this religion sees this kind of evidence, what do they do? Do they believe that he is a trickster, or disbelieve the claims? If they believe the claims, do they go away from the religion, go back to traditional Hinduism etc? Thanks"

As expalined, followers are from many faiths. May be majority is from hindus. Again, the follwers  follow him in spite of all the negative publicity he is getting. Nobody goes back to "his faith". Stays put with S/he believes and wants to believe. That is all. The question is based on the assumption that all are hindus, convetional or otherwise. This is not correct as said above.  

Secondly, there's is nothing known as "traditional hinduism". Firstly hinduism is not a single religion or faith in the conventional sense. It is a bundle of several faiths, that evolved over the centuries. Possible division may be orthodoxists, modernists, conventionalists etc. There're those who swear by scriptures and several who don't; those who are atheists as well. And finally, faith, any faith, is kind of "blind". In the sense that it cannot be rationalised or explained. It is just there that's all. Many are just born into one or the other faith; some convert, reconvert etc. But still the basic faith is "blind". Problem, sometimes very serious problem arise, when some claim that their faith is superior or their god is real etc. Conflicts rise. Cruel joke is this is all out of "blind" faith!!!    

"So long as it does not harm anyone, including yourself, do as you please." [A Wiccan adage]   
Love & God Bless.
P.S: This board has been silent for quite some time. hence I thought of responding to the question posed here.