What iron-clad reason did Dumbledore have for believing Snape was on his side? Maybe he was a good actor and a double agent. Was it just that he loved (or pretended to) Lily or he used legilimency?
Dumbledore believed Snape because he saw how devastated he was after having betrayed Lily. At that moment, Snape swears to do anything and everything to get revenge at Voldemort, to defy him.
Maybe Dumbledore additionally used legilimency and saw Snapes true emotions. But there is no canon evidence for that.
Additionally, every time someone noticed someting suspicious about Snape and told Dumbledore, he already knew it because Snape told him himself or he had told Snape to do so (stopping Quirrel, the Unbreakable Vow, pretending to help Malfoy).
Adding something more to the answers.
The important thing to remember here is that everyone, including Snape, believed Voldy was dead.
The following excerpt from HP & the Deathly Hallows - chapter Prince's Tale. Conversation between Dumbledore & Snape in Snape's memories
"You know how and why she died. Make sure, it was not in vain. Help me protect Lily's son"
"He does not need protection. The Dark Lord has gone - "
" - The Dark Lord will return, and Harry Potter will be in terrible danger when he does"
Snape loved Lily. That is the Iron Clad truth. IIRC, Snape, after having mentioned the Prophecy to Voldy, pleaded him to let Lily live & only kill Harry & his father.
Snape was not the kind of person to follow Voldy out of fear. Snape was ambitious & looked up to Voldy. Voldy could have yanked Lily away & killed Harry & let her live. But he didnt care. Snape was obviously devastated. And Voldy was gone, so no double agent opportunities were yet presented to him.
When Dumbledore tells him that Voldy will return & the boy, who has Lily's eyes, would be in great danger, Snape has an opportunity to redeem himself, avenge his love & prove his love for Lily more to himself than anyone else
First, the fact that Snape provided information which proved to be legit about his master's intent to kill the Potters. Snape betrayed Voldemort - who was then at the height of his power - to trying to save Lily. That alone tells enough about Snape's priorities.
His remorse story was also plausible, considering Severus's friendship with Lily till their 5th year. What kind of bigoted blood supermacist has a muggleborn for best friend for years? A conflicted one, who puts his feelings above his ideology.
Then, after Lily's death, Dumbledore witnesses him falling to pieces. That's a pretty dramatic performance for an usually reticent guy, but sure, it might have been just that, a show to gain Dumbledore's trust. Unlikely, but it was possible. But later Snape proved his words with actions: In Harry's first year Snape protects him and does everything to assist Dumbledore to get rid of his former master. And continues to do so all the following years.
Snape never gave Dumbledore any reason to doubt his motivations, and was very useful and competent. It seems from their dialogues in DH, The Prince's Tale that they had a good 'work relationship' and cautious and secretive Dumbledore, who usually played with his cards close to the chest, and was reluctant to give more than the the essential information, preferring to speak in riddles and giving mere hints, did trust Snape, his conclusions based on observations for years he knew Snape, and so he was fairly open with him.