Other than what Skooba has mentioned, there's one other thing to consider. The legal loopholes are an alternative explanation.
House Tarth was sworn to House Baratheon of Storm's End and held the Isle of Tarth in the name of Lord of Storm's End.
Yet, Why does that mean that Brienne owes her fealty to House Baratheon? She is not the Lady of Tarth yet and has therefore no inherent allegiance to the Lord of Storm's End. That's for her father to do, Lord Selwyn Tarth. When Lord Selwyn dies, only then Brienne becomes a vassal of Lord of Storm's End.
Until then, she is a free agent who can swear fealty to anyone she likes. It is in any case not a definite thing that Brienne will remain heir to Lord Selwyn. If Lord Selwyn sires a son, that means Brienne is no longer the heir as sons come before daughters in succession.
And of course there's the matter of her vows as a Rainbow guard as well.
Brienne's personal preference and Vows as a Rainbow guard
Also there is personal preference as well. Brienne does not want to be Lady of Tarth. She only wants to be a Knight. Remember, she was a Rainbow guard of Renly, equivalent to King's Guard. King's Guard forfeit their claims on all lands and titles when they swear their vows. So in any case, after swearing her vows, Brienne is plausibly no longer the heir to Tarth Isles and is therefore not obligated to swear fealty to Lords of Storm's End.
How and why she swore fealty to Catelyn?
Brienne did not right away pledge fealty to Lady Catelyn as you suggest. She wanted to show her gratitude by safely escorting her to Riverrun and then return to Stormlands to avenge Renly Baratheon. But Catelyn convinced her that Brienne's attempts will be futile as of then so she should instead serve her son, Robb, who will most likely face Stannis sooner or later.
Brienne however preferred to swear fealty to Catelyn instead because Robb was a stranger to her and she had come to admire Catelyn.
As shown in the Season 2 Episode 5, The Ghost of Harrenhal:
Brienne: Once you're safely back amongst your own people, will you give me
leave to go, My Lady?
Catelyn: You mean to kill Stannis.
Brienne: I swore a vow.
Catelyn: But Stannis has a great army around him. His own guards are sworn to
keep him safe.
Brienne: I'm as good as any of them. I should never have fled.
Catelyn: Renly's death was no fault of yours. You served him bravely.
Brienne: I only held him that once as he was dying.
Catelyn: He's gone, Brienne. You serve nothing and no one by following him into
the earth. Renly's enemies are Robb's enemies as well.
Brienne: I do not know your son, My Lady... but I could serve you if you would
have me. You have courage. Not battle courage, perhaps, but, I don't
know, a woman's kind of courage. And I think that when the time comes,
you will not hold me back. Promise me that you will not hold me back
Catelyn: When the time comes, I will not hold you back.
Brienne: Then I am yours, My Lady. I will shield your back and give my life for
yours if it comes to that. I swear it by the Old Gods and the new.
Catelyn: I vow that you shall always have a place in my home and at my table
and that I shall ask no service of you that might bring you dishonor.
I swear it by the Old Gods and the new.
As evident from this conversation, Brienne swore fealty because:
- She admired Catelyn's courage.
- She understood the futility of her cause.
- Starks provided her a hope for avenging Renly.
- She had plausibly forfeited her claims on her family lands after swearing vows of Rainbow guard.
In the books however, it is traditional that the Lords and their heirs owe their fealty to their overlords. It is evident from the conversation of Ser Robar Royce1 and Catelyn Stark:
“You are a long way from the Vale, ser,” she told him.
“And you far from Winterfell, my lady.”
“I know what brought me here, but why have you come? This is not your
battle, no more than it is mine.”
“I made it my battle when I made Renly my king.”
“The Royces are bannermen to House Arryn.”
“My lord father owes Lady Lysa fealty, as does his heir. A second
son must find glory where he can.” Ser Robar shrugged. “A man grows
weary of tourneys.”
A Clash of Kings - Chapter 31 - Catelyn
But in any case, since most probably Brienne is no longer heir to the Isles of Tarth, she owes no fealty to her father's overlord.
1. Robar Royce was second son of Lord Yohn Royce of Runestone, a prominent vassal to House Arryn of Eyrie