I just figured that as a poor, abused child, she had never experienced it. We only really ever see characters who either have magic themselves (Granny, Ruby, the Dwarves, Zelena) or are royalty and have better access to the world around them. Cinderella is one of the few characters who is completely normal. The only other character would be Cora in The Miller's Daughter, but we don't know for sure that she believed in magic before meeting Rumple. Zelena's adoptive mother didn't believe her husband when he claimed Zelena used magic, so she might not know it exists. Etc.
Also, Lola, Gus-Gus (or any other equivalent mouse) is not magical in most versions of Cinderella. Presumably, this one is the same.