We never see Catelyn and Arya interact with one another in the series, their relationship isn’t highlighted in the same vein as Arya and Ned’s relationship or Jon and Arya’s relationship. The best way we can get somewhat of an understanding of their relationship is through their thoughts and words of one another. I don’t agree that they didn’t get along with one another, we never hear of any incidences where they fought or were cold with each other. I think the issue in their relationship stems from Arya’s wildness and Catelyn’s attempts to reign in that wildness. Catelyn is well aware of how harsh their society is on girls who do not fit the mold (is there any creature on earth as unfortunate as an ugly woman?) and I think she was honestly trying to turn Arya into a lady for her own benefit. Arya was always bullied for her looks, always reminded that she wasn’t as beautiful as her sister, or as talented at the womanly arts as her sister, and I think Catelyn wanting Arya to be more lady-like translated rather negatively for Arya. But it is clear that Catelyn loved Arya dearly, just as Arya loved her mother dearly and held her in high regard.
Catelyn’s thoughts on Arya’s appearance, manners, and her distinctly unladylike ways:
Sansa would shine in the south, Catelyn thought to herself, and the gods knew that Arya needed refinement.
Arya had always been harder to tame. Perhaps Cersei was reluctant to parade her in open court for fear of what she might say or do. They might have her locked safely out of sight. Or they might have killed her. Catelyn shoved the thought away.
"And Arya, well…Ned’s visitors would oft mistake her for a stableboy if they rode into the yard unannounced. Arya was a trial, it must be said. Half a boy, half a wolf pup. Forbid her anything and it became her heart’s desire. She had Ned’s long face, and brown hair that always looked as though a bird had been nesting in it. I despaired of ever making a lady of her. She collected scabs as other girls collected dolls, and would say anything that came into her head. I think she must be dead too.” When she said that, it felt as though a giant hand were squeezing her chest.
Lady Catelyn had said that Arya lacked her sister’s beauty.
I do think it was rather harsh of Catelyn to say such a thing to Brienne, however, every time Catelyn thinks of Arya in such a manner, it is always followed by sadness and grief at the thought that she may be dead, that she may be lost and she’ll never see her again.
Catelyn praying for Arya:
She went to the Maid and beseeched her to lend her courage to Arya and Sansa, to guard them in their innocence.
The Warrior was Renly and Stannis, Robb and Robert, Jaime Lannister and Jon Snow. She even glimpsed Arya in those lines, just for an instant
I think it’s really interesting that Catelyn sees Arya in the warrior’s statue. The warrior is seen as the embodiment of strength and courage, of which both Arya and Catelyn have an abundance of, and I think Catelyn seeing Arya in the warrior was a way for her to remember these qualities in Arya; perhaps even providing her with a small amount of comfort and hope that Arya may still be alive precisely because of these attributes.
Catelyn on Arya [and Sansa’s] importance:
" … but not for the girls?" Her voice was icy quiet. "Girls are not important enough, are they?"
There are many times that Catelyn reflects and mourns that Arya is either lost to her forever or dead, she goes back and forth on this actually. When Robb is making his will, she actually reminds him that Arya could be his heir:
“I agree that the north must not be permitted to pass to the Imp, but what of Arya? By law, she comes after Sansa … your own sister, trueborn … “
For Arya, her thoughts of her mother have always been about how much she misses her, how much she wants to save her, or how worried she is that her mother may not want her back because of her appearance and the things she has had to do in order to survive.
Arya missing her mother/remembering her mother/wanting to save her mother:
she yearned to see her mother again…
When she thought of seeing Robb’s face again Arya had to bite her lip. And I want to see Jon too, and Bran and Rickon, and mother. Even Sansa… I’ll kiss her and beg her pardons like a proper lady, she’ll like that.
we have to go get my mother […] maybe we can save her
-Arya at the RW, ASoS
It was her mother she wanted, not her mother’s sister.
We should go back to the Twins and get my mother. She can’t be dead. We have to help her.
that night she went to sleep thinking of her mother, and wondering if she should kill the Hound in his sleep and rescue Lady Catelyn herself. When she closed her eyes she saw her mother’s face against the back of her eyelids. She’s so close I could almost smell her…
you should have saved my mother
"Needle was Robb and Bran and Rickon, her mother and her father, even Sansa…"
Arya worrying or reflecting on her appearance, and what her mother might think of her:
Arya looked down at her ragged clothes and bare feet, all cracked and calloused. She saw the dirt under her nails, the scabs on her elbows, the scratches on her hands […] “my mother’s a lady, and my sister, but I never was.”
And her lady mother, what would she say? Would she still want her back, after all the things she’d done? Arya chewed her lip and wondered.
“My hair’s messy and my nails are dirty and my feet are all hard.” Robb wouldn’t care about that, probably, but her mother would. Lady Catelyn always wanted her to be like Sansa, to sing and dance and sew and mind her courtesies. Just thinking of it made Arya try to comb her hair with her fingers, but it was all tangles and mats, and all she did was tear some out…”
The Hound had hacked handfuls of her hair off only two days past. He was an even worse barber than Yoren, and he’d left her half bald on one side. Robb won’t know me either, I bet. Or even Mother.
Her mother used to say she could be pretty if she would just wash and brush her hair and take more care with her dress, the way her sister did.
It speaks to both Arya’s low self esteem and the unfair patriarchal standards of Westeros that she questions whether her own mother would accept her, simply because she is dirty, grimy, and nothing at all the lady that Catelyn wanted her to be. Of course, we know that Catelyn missed Arya immensely, and tried her damndest to get her back, but it’s quite sad that Arya is doubtful of this in the first place. In my opinion, Catelyn wanting Arya to be like Sansa, to be more refined, was out of a place of love, because she knew it would make Arya’s life much harder and more painful if she grew up to be something of an oddity to the severe standards for girls and women (just look at how she sympathizes with Brienne’s lack of beauty). I do think Cat could have shown Arya more positive support though, but that’s just my opinion.
I also find Arya’s loyalty and protectiveness of her mother really endearing. She gets angry when the brotherhood talk of Catelyn freeing Jaime:
it’s not true, thought Arya. It couldn’t be true […] she had promised Harwin she would not try and run away again, she knew, but that was before they started telling lies about her lady mother.
And she’s protective and defensive of both her father and mother when she becomes adamant that her father loved her mother, and only her mother, when Ned Dayne tells her about the possibility of a relationship between Ashara Dayne and Ned Stark:
that’s not so he loved my lady mother […] she was the only one he loved
Cat and Arya may not have had the most perfect relationship, and Arya may have had a closer relationship and bond with her father, but the fact remains that they both loved and missed each other a great amount, and there’s not a whole lot of evidence in the text to suggest that their relationship was troubled or strained or that they didn’t get along.