TL;DR: It appears that woman do change their names upon marriage though there are some caveats.
I'm pretty sure this won't be answered from the show so I'll use the books.
Catelyn Stark is referred to as Catelyn Stark at least once in the books, after a very brief search and it is in her own POV chapter:
Catelyn Stark stared at the eunuch in stunned disbelief. He was a spider, she thought wildly, an enchanter or worse. He knew things no one could possibly know, unless … "What have you done to Ser Rodrik?" she demanded.
A Game of Thrones - Catelyn IV
So it would appear that woman do change their names upon marriage just like in our world.
However, Jon appears to call her by both names from his POV chapter:
Something cold moved in her eyes. "I told you to leave," she said. "We don't want you here."
Once that would have sent him running. Once that might even have made him cry. Now it only made him angry. He would be a Sworn Brother of the Night's Watch soon, and face worse dangers than Catelyn Tully Stark. "He's my brother," he said.
A Game of Thrones - Jon II
Littlefinger also calls her Tully but he wants her for his own and so probably does it to try and weaken her marriage to Ned in his own eyes:
"Just what it appears," Littlefinger said, easing himself onto a window seat. "A brothel. Can you think of a less likely place to find a Catelyn Tully?" He smiled. "As it chances, I own this particular establishment, so arrangements were easily made. I am most anxious to keep the Lannisters from learning that Cat is here in King's Landing."
A Game of Thrones - Eddard IV
Also note this quote from the books which seems to imply that she has changed her name:
"Lady … Stark?" Masha Heddle said thickly.
"I was still Catelyn Tully the last time I bedded here," she told the innkeep. She could hear the muttering, feel the eyes upon her. Catelyn glanced around the room, at the faces of the knights and sworn swords, and took a deep breath to slow the frantic beating of her heart. Did she dare take the risk? There was no time to think it through, only the moment and the sound of her own voice ringing in her ears. "You in the corner," she said to an older man she had not noticed until now. "Is that the black bat of Harrenhal I see embroidered on your surcoat, ser?"
The man got to his feet. "It is, my lady."
A Game of Thrones - Catelyn V
On further inspection the show seems to back this up. Here's a quote from I believe Tyrion, though I'd have to re-watch to find out:
What happened here? Where is Lady Stark? Why didn't she receive me?
She wasn't feeling well.
Game of Thrones, S01 E04, "Cripples, Bastards, and Broken Things"
There is also this quote from when Cat arrives at Kings Landing:
Welcome to King's Landing, Lady Stark.
Would you mind following us?
We've done nothing wrong.
We've been instructed to escort you into the city.
I don't know who's providing your instructions, but Follow me, Lady Stark.
Game of Thrones, S01 E03, "Lord Snow"
And every other reference I've found about Cat in show she has been called Stark.
This related question: Why is Cersei commonly referred to as "Cersei Lannister" instead of "Cersei Baratheon"? Focuses on woman marrying into royalty and in this case it appears that the woman don't take on their husbands name.
I've also found this quote on the Game of Thrones wikia though I don't know where it is sourced from:
Among the powerful noble families of the Seven Kingdoms, women will retain the use of their maiden name if their family is more powerful or ancient than their husband's family.
Further down it seems to imply that Sansa did not become Sansa Lannister upon her marriage to Tyrion:
Given that the Starks and Lannisters were both Great Houses of equal social rank, both former royal houses, it therefore isn't automatically assumed that Sansa would switch to being known as "Sansa Lannister".
Also as the Starks are of greater power than the Boltons it would imply that she also did not become Sansa Bolton upon her marriage to Ramsey.