House Tully rules over the Riverlands from their ancestral seat of Riverrun. The Riverlands used to be ruled from by people from The Iron Isles but that ended a few centuries ago when the cruel King Harren the Black of The Iron Isles thought it was a good idea to fight against the Targaryen invaders and their dragons. After King Harren was roasted to a crispy crisp at his castle, the Targaryens raised the Greyjoys to rule the Iron Isles, and granted overlordship over the Riverlands to the Tullys, who had been prudent enough to support the Targaryens and revolt against the late and unlamented Harren.
The Riverlands are a nice place to visit and live but unfortunately they are not easily defensible. They are centrally located. Besides the aforementioned rivers, there aren't any natural barriers to prevent invasion. Many warring armies have always considered the Riverlands a great place to settle their differences. So House Tully, currently presided over by Lord Hoster Tully, has always been keen to ally itself with other Houses. Lord Tully wed his older daughter Catelyn to Ned Stark and his younger daughter Lysa to Jon Arryn, each heads of their Great Houses. Lord Tully hasn't yet arranged a wedding for his son and heir Edmure, while his younger brother Brynden has steadfastly refused all of Hoster's suggestions, leading to a rift between the two men.
Brynden, more than anyone else, is the military leader of House Tully. House Tully supported Robert's Rebellion as Catelyn Stark was originally betrothed to Ned's older brother Brandon, who was murdered by the Mad King. Catelyn and Ned's marriage was unusual among arranged pairings in that they actually grew to love each other. Like most Houses in the South the Tullys adhere to the faith of the Seven.
After Catelyn Stark arrested Tyrion Lannister on her father's lands and did so in part in her father's name, Tywin Lannister sent raiding parties to kill, rape and pillage in the Riverlands. After Ned Stark's death Robb Stark came to his maternal relatives' defense and since then it's been a major slugfest between the Tullys and Starks on one side and the Lannisters on the other. Robb Stark has made a few attacks into the Lannister Westerlands and soundly trashed every Lannister army he's come up against. But he doesn't yet have the strength to evict the Lannisters from his mother's homeland or properly besiege the Lannisters on their home turf. So as usual, it's the so-called smallfolk of the Riverlands who are suffering the most. As House Tully supports House Stark's secession from the Seven Kingdoms, as far as the Iron Throne is concerned they are also rebels who should be hanged, drawn and quartered. The House Tully words are "Family, Duty, Honor", which unsurprisingly is pretty much how Catelyn views her responsibilities and the world in general.
You might call this House the (insert class based slur for slow-witted unhygienic rural inhabitants) of Westeros. They rule over a relatively inhospitable area of Westeros, The Iron Isles. They worship The Drowned God (something alien to everyone else in Westeros). Their ways and cultures are quite different. The biggest sticking point between the peoples of the Iron Isles and the mainland is that the folks of the Iron Isles consider violence not only to be normative but also something of a religious requirement. A man who routinely obtains goods or wealth thru trade or business or purchase is considered, at best unmanly and at worse something of a heretic. The proper way of obtaining goods goes something like this. If you want something, you stab its current owner in the neck and take it. This is called paying the Iron Price. It is also why nobody in Westeros who's in their right mind likes or trusts the Greyjoys or anyone from the Iron Isles. It is why Catelyn Stark was so vociferous in telling her son Robb not to let Theon Greyjoy go or trust Balon Greyjoy. If you remember once she heard of the Greyjoy attack on the North she could not prevent herself from telling Robb "I told you so!!".
This House is currently led by the bitterly resentful Balon Greyjoy, who appears to have disinherited his last remaining son, Theon in favor of his daughter (Asha in the books, Yara in the HBO show). Balon also has some equally vile younger brothers. Theon's alarm over his sister's rise in their father's affection is part of what led him to join in on the attack on the North and specifically to try to outdo Yara by taking Winterfell.
The one thing that House Greyjoy is known for, besides being a sniveling bunch of psychotic backstabbers, is that they have perhaps the continent's best fleet and are considered to be Westeros' finest sailors. If Balon Greyjoy had accepted Robb Stark's offer and attacked the Lannister Westerlands or King's Landing, events in Season Two may have proceeded quite differently. But woulda, shoulda, coulda. It is impossible both culturally and psychologically for Balon Greyjoy to accept "gifts" or friendly behavior from other people. As we saw in Season 2 , Theon Greyjoy has good reason to dislike his father, as if it weren't for his father's failed revolt more than a decade earlier Theon would never have been taken as a
Their House words are "We Do Not Sow" which is a reference to their utter disdain for doing any work other than killing people and taking their stuff. They rule from their seat of Pyke.