Not all story songs, but my kids (who are now 37) liked:

Hopalong Peter (PD, learned from NLCR)
I'm Gonna Tell (Rosalie Sorrels)
Barnyard Dance (Carl Martin & Howard Armstrong)

A couple of non-kids songs that they loved me to sing:
Spanish Pipe Dream/Blow Up Your TV (John Prine)
Mamas, Don't Let Your Babies Grow Up To Be Cowboys (Patsy & Ed Bruce)

Already mentioned:
Frog Went A Courting (learned from my dad singing it to me)
My dad sang two last verses that I've never heard anyone else sing, but he said that was the way his mom sang it:

They paddled off across the lake, uh huh.
They paddled off across the lake
And got swallered up by a big black snake, uh huh.


Well, that was the end of him and her, uh huh.
That was the end of him and her
Now we won't have tadpoles covered in fur, uh huh.

Two real stories with songs attached that they also liked were The Foolish Frog and Abiyoyo. While they would get me to do these sometimes, they really enjoyed Pete Seeger's versions.