Skooba has added a good answer but there is one thing that he has not mentioned from the book's perspective. Since you have added the books tag, I suppose I should mention it.
Why choose Renly?
In Books, Northerners didn't know (At that time) the whole story about Joffrey being a bastard. For them, both Stannis and Renly were pretenders, out there to usurp their nephew's throne.
For them the choices were:
- King Joffrey, who murdered Eddard.
- Prince Tommen, another one born out of Cersei Lannister, therefore no less a Lannister as pointed out by the Riverlander Lords when Robb said that Tommen is the heir of Joffrey.
- Lord Stannis, the sour and strict lord who had very small number of troops or resources to offer but had a better claim than his brother.
- Lord Renly, the cheerful, well dressed and beloved brother of the late King who had a massive Army but not a very good claim.
They were considering their options in AGOT Catelyn IX:
Lord Jonos Bracken rose to insist they ought pledge their fealty to King Renly, and move south to join their might to his.
“Renly is not the king,” Robb said. It was the first time her son had spoken. Like his father, he knew how to listen.
“You cannot mean to hold to Joffrey, my lord,” Galbart Glover said.
“He put your father to death.”
“That makes him evil,” Robb replied. “I do not know that it makes
Renly king. Joffrey is still Robert’s eldest trueborn son, so the
throne is rightfully his by all the laws of the realm. Were he to die,
and I mean to see that he does, he has a younger brother. Tommen is
next in line after Joffrey.”
"Tommen is no less a Lannister," Ser Marq Piper snapped.
"As you say," said Robb, troubled. "Yet if neither one is king, still,
how could it be Lord Renly? He's Robert's younger brother. Bran can't be Lord of Winterfell before me, and Renly can't be king before
"Renly is crowned," said Marq Piper. "Highgarden and Storm's End
support his claim, and the Dornishmen will not be laggardly. If
Winterfell and Riverrun add their strength to his, he will have five
of the seven great houses behind him. Six, if the Arryns bestir
themselves! Six against the Rock! My lords, within the year, we will
have all their heads on pikes, the queen and the boy king, Lord Tywin,
the Imp, the Kingslayer, Ser Kevan, all of them! That is what we shall
win if we join with King Renly. What does Lord Stannis have against
that, that we should cast it all aside?"
“The right,” said Robb stubbornly. Catelyn thought he sounded
eerily like his father as he said it.
So until that point, Robb was predisposed towards Lord Stannis instead of Renly. It was Great Jon Umber's Proclamation which changed everything. Quoting from the same chapter:
“MY LORDS!” he shouted, his voice booming off the rafters. “Here is
what I say to these two kings!” He spat. “Renly Baratheon is nothing
to me, nor Stannis neither. Why should they rule over me and mine,
from some flowery seat in Highgarden or Dorne? What do they know of
the Wall or the wolfswood or the barrows of the First Men? Even their
gods are wrong. The Others take the Lannisters too, I’ve had a
bellyful of them.” He reached back over his shoulder and drew his
immense two-handed greatsword. “Why shouldn’t we rule ourselves again?
It was the dragons we married, and the dragons are all dead!” He
pointed at Robb with the blade. “There sits the only king I mean to
bow my knee to, m’lords,” he thundered. “The King in the North!”
Now the Northmen were not looking for an Overlord, who had to have a good claim to the throne. Now they were independent, negotiating as equals and had to find an ally who could help them. The logical choice was King Renly who had Stormlands and the Reach behind him.
Whose Idea was the alliance with Renly?
Skooba has already correctly pointed out that It was Catelyn who knew what to do when news of another Lannister Army reached them.
Did Stannis know about Eddard's loyalty?
Not to mention, The quote you mentioned is a show only thing. In Books, Stannis never knew that Lord Eddard was in favor of his claim.
As already mentioned by Skooba, this is how it went:
Stannis studied her face. “And what cause brings you to this field,
my lady? Has House Stark cast its lot with my brother, is that the way
This one will never bend, she thought, yet she must try nonetheless.
Too much was at stake. “My son reigns as King in the North, by the
will of our lords and people. He bends the knee to no man, but holds
out the hand of friendship to all.”
Catelyn didn't stay quiet. She answered Stannis frankly and showed that she and her lot did not know about the dark truth behind Joffrey's parentage:
Stannis frowned at her. “You presume too much, Lady Stark. I am the
rightful king, and your son no less a traitor than my brother here.
His day will come as well.”
The naked threat fanned her fury. “You are very free to name others
traitor and usurper, my lord, yet how are you any different? You say
you alone are the rightful king, yet it seems to me that Robert had
two sons. By all the laws of the Seven Kingdoms, Prince Joffrey is
his rightful heir, and Tommen after him... and we are all traitors,
however good our reasons.”
ACOK- Catelyn III