Q: What are the actual origin and history of the name she oak or sheoak?
This was likely named by the British Royal Navy who sailed around and wrote early narratives of Australia. Ships of sail are in need of wood, so they used familiar names to help describe the trees they found. She-oak was named after oak due to their similar timber texture.
The name appears to have originated from Sydney. The narrative of a voyage of discovery by Lieutenant James Grant, 1803 (and similarly by Grant, 1804):
The trees we saw were in general what is termed she-oak about Sydney.
Lieutenant J.H. Tuckey's An Account of a Voyage to establish a colony at Port Phlip, 1805:
The timber, within five miles of the beach, is chiefly the she-oak, only fit for cabinet-work ; the other kinds of timber-trees are very thinly scattered.
Observations of the various Kinds of Timber found in New South Wales. From Tuckey's Voyage, 1805:
New South Wales produces a great variety of timber trees, to some of which the colonists have given names descriptive of their qualities; and others they call by the names of those trees which they most resemble either in leaf, in fruit, or in the texture of the wood. Among the former are the blue, red, and black butted gums; stringy and iron barks; turpentine and light wood: and among the latter are the she-oak, mahogany, cedar, box, honeysuckle, tea-tree, pear-tree, apple-tree, and fig-tree. These trees shed their bark annually at the fall of tic year, and are always in foliage, the new leaves forcing off the old ones.
Q: How is "a comparison of the timber quality with English Oak" relevant to the name?
Many Casurina trees have been given oak names, not due to their appearance, but their timber.
Naturalist George Bennett's Wanderings in New South Wales, Batavia, Pedir Coast, Singapore ..., Volume 1, 1834:
The "swamp oak" [Casurina paludosa] bears much resemblance to the larch-I know not why this and other species of the casuarina trees have received the colonial appellation of "oaks," as forest-oak, swamp-oak, she oak, &c, as they have not the slightest resemblance to that tree in external character, unless the name may have been given from some similarity in the wood.
Martin Montgomery's History of the British colonies, 1835:
Casuarina Equisetifolia, horsetail casuarina, or he and she oak. — Monoecia monandria, nat. ord. Casuarinea. ... with leaves, or rather branchlets, hanging down in bundles, from 12 to 18 in length, like a long load of hair or horse's-tail... The wood is brittle, but makes very handsome furniture.
Among the ornamental woods come light wood, she-oak or beef tree, honeysuckle, myrtle, and the cherry-tree.
beef wood — she oak tree (Casuarina stricta); swamp oak tree (Casuarina paludosa); forest oak tree (Casuarina torulosa);
Q: Was there actually a "Native American" influence in forming the name of an Australian tree?
The OED claims the American sheac connection is baseless, but William Mann repeated the claim in 1839:
Causarina torulosa—She-oak. C. stricta—He-oak. C. tenuissima—Marsh Oak.—The name of the first of these is said to be a corruption of Sheac, the name of an American tree producing the beef-wood, like our She-oak. The second species has obtained the name of He-oak, in contradistinction of She-oak.
Q: And for extra points, explain why the Ngarrindjeri have a separate word, kula, for male she oak trees.
This is really for Ngarrindjeri Language and Usage, but Diane Bell's Ngarrindjeri wurruwarrin: a world that is, was, and will be says:
I've read about this tree in Tindale and much of it concerns sacred matters which are not discussed openly. What can be said is that tungi, the female she-oak, marked with colour and considered sacred, are distinguished from kula, the male she-oak tree