Vulcan genitalia (particularly male) has been a subject of great fannish interest for many decades.
Vulcan female genitalia, a rare topic, from Grup #1 (1972)
In The World of Star Trek (Ballantine, 1973), David Gerrold wrote about what he felt to be bizarre fan letters received by the creators of the show. Among them was a missive several pages long from an older woman who very carefully explained that she was married and this was not prurient interest, but that as red-blooded creatures have pink extremities, what she wanted to know about Spock -- "with reference to particular extremities -- if they were green." Gerrold added, "Yes, they," and added that the letter had been passed around for laughs and "idle speculation around the set had it that the particular extremity this woman was inquiring about was forked."
In her book On The Good Ship Enterprise, Bjo Trimble said her husband saw the letter and understood that "they" to referred to testicles, not anything more exotic. However, fan speculation about Spock's sexual anatomy probably started with, and was influenced by the highly publicized "they," of that letter.
Fanon: Male Genitalia
In the early years of Star Trek fandom, speculations on Vulcan anatomy were more general and centered around the differences in internal organs as revealed by Dr. McCoy in various episodes. Since Amanda appeared to enjoy a happy married life with Sarek, fans tended to assume that Vulcan sexuality did not differ significantly from human in that regard (allowing for the pon farr cycle). Humans and Vulcans could be sexually compatible even if conceiving a child required scientific intervention. Even the sexually explicit illustrations in Grup revealed Spock with a perfectly normal-looking penis. It was not until fan writing shifted predominantly to K/S that widespread speculation on the alien nature of Spock's genitalia really took off. Fans imagined them to be as alien as his ears and as green as his blood. This was almost unique to Star Trek fandom.
Double Ridged Penis
Specifics varied, but many K/S writers copied the idea that Spock's penis was green and had double ridges, that is a double glans, as opposed to a human male's single ridge or glans.  Gayle F invented this version in her early Kirk/Spock stories and illustrated it in her fanart. According to Gayle F, the first appearance of the double ridges was in Desert Heat, the first story of the Cosmic Fuck Series, first published in The Sensuous Vulcan (1977) and Gayle says in her author's note at the K/S Archive that the story was probably completed in 1976.
From the Cosmic Fuck Series: "Descending to the dark thatch where the swollen genitals lay, mossy green, engorged with blood. The double ridges on the head seemed strangely decorative. Increased stimulation? Nature had her own logic."
In a 2013 interview, Gayle said:
Okay. I don't remember the exact reason I picked that other than I decided I wanted Spock to have, you know, an alien cock, but I wanted it to be beautiful. And, I guess I just ran through some designs in my head, and that was a very elegant double-ridged cock that could be drawn very nicely, you know, nothing too weird or H.P. Lovecraftian. (laughter) ... And it wasn't so alien that it would put people off even if it wasn't, you know, Lovecraft. So it was just, you know, it looked like of human except more interesting... I think everybody, everybody liked it because it was elegant... It suited him. It went with the ears so nicely. (laughter) 
Here are a few examples of Gayle's fanart showing Spock's alien penis with the double ridges -- click on image to enlarge:
Cover of The Price and The Prize (1981). Note: Marked as sexually explicit; minimized.
Back cover of First Time #18 (1988). Note: Marked as sexually explicit; minimized.
Cover of First Time #10 (1987). Note: Marked as sexually explicit; minimized.
Inside art from Choices (1986). Note: Marked as sexually explicit; minimized.
Cover of T'hy'la #3 (1983). Note: Marked as sexually explicit; minimized.
Back cover of Obsc'zine #4 (1980). Note: Marked as sexually explicit; minimized.
Back cover California K/S #1 (1984). Note: Marked as sexually explicit; minimized.
Hidden Behind a Furry Mound: The Stamen
In The Matchmaker (1985) by Janet Alyx (T'hy'la 5), Spock's penis is hidden behind a furry mound that becomes swollen and unfolds like petals of a flower and sprouts a bright green penis that unfolds like a stamen.In Mirrors of Mind and Flesh (1979), Kirk explores his new lover:
Let's see what it looks like, Spock,' Kirk said as he knelt, peeling the briefs over Spock's hips. He laughed softly as he surveyed the alien design. 'Almost like a woman.' Spock shivered as Kirk's fingers rubbed the soft, furred lips of the genital pouch, centered high on the pubic mound. Lips so swollen and sensitive now. Kirk's thumbs slid along the moist inner surface of the labia, parted, opened them, revealing the rounded head of the cock, a glistening green jewel framed within. Kirk's breath touched him there, moist and tickling. Spock felt the first head begin to come forth, shy, eager, responding to that delicate touch.
Great Green Anthurium & Tentacles: The Fra'ls
Other notable fanon genitalia for Spock included the great green anthurium invented by Leslie Fish in her early Kirk/Spock story Poses (1977). This version included two handling tentacles which later became known as fra'ls.
In Poses, Spock explains that the fra'ls are like anchors to hold and stimulate one's partner:[In Poses]... there are five illos by Leslie, including a captivating one of another version of Spock’s alien genitalia. Here Spock has an “orchid-anthurium” that consists of a pouch formed by three protective petals that peel back to reveal “glistening chartreuse surfaces studded with hyper- sensitive spots of darker green, the two side-tendrils gracefully uncoiling to stand like oiled sepertine [sic] honor-guards beside the rising, proud, gleaming central shaft.” (Later these were given the fan name of frals and used in several stories.) In this version, testes in Vulcans are internally located on either side of the spine in the small of the back. 
There . . . there . . . I'll show you . . ." Kirk repeated, stroking steadily at the tender, changing flesh. Fascinated, he watched the three petals curl back to reveal glistening chartreuse surfaces studded with hypersensitive spots of darker green, the two side tendrils gracefully uncoiling to stand like oiled serpentine honor guards beside the rising, proud, gleaming central shaft. "Like an orchid," Kirk whispered, "or a cross between . . . an orchid and a great green anthurium . . .. Oh, it's beautiful! What are these two things for?" He ran his fingers along the wet, quivering tendrils.
Poses also describes Spock's testes as located in the lower back: "'Spock blushed. Shyly, he took Kirk's free hand and guided it carefully to the small of his back, placing the fingers two inches apart, on either side of the spine.In A 2007 Interview with Leslie Fish, Fish explains:
I wanted to remind people that Vulcans are aliens — humanoid, yes, but not human. Ted Sturgeon had already broken ground for that in “Amok Time,” with his fascinating concept of Vulcan sexuality, and I decided to go further with details of Vulcan physiology. Why, after all, should an alien — even a humanoid alien — have sexual equipment exactly like a human’s? Goddess knows, terrestrial animals differ widely enough that an alien should differ further. All we knew about Vulcan sexuality, at that point, was that: a) it’s cyclical, it’s the males rather than the females who cycle, and the male must have some manner of physical discharge or else “the tensions will simply kill him”; and b) it’s possible for a Vulcan male to mate successfully with a human female. Okay, now all that’s necessary for (b) is some sort of projective organ capable of getting into a human vagina and depositing genetic material there — and everything else can vary tremendously. Concerning (a), the Vulcan male must have some way of physically rewarding the Vulcan female for putting up with his desperate desires, not to mention the effort and dangers of pregnancy, so there must be something besides simple penetration which provides “unendurable pleasure, indefinitely prolonged” for the female. Now there’s one sexual feature which appears in all known female mammals which has absolutely no other discernible purpose than providing sexual pleasure, and that is the clitoris. If Vulcan males are enough like human males to mate and breed with human females, then there must be an equivalent organ among Vulcan females. If so, then the easiest physical way to reward the female for her sexual compliance had to be some organ capable of stimulating the clitoris — and thus those “tendrils” evolved. Ah, but if the female could stimulate the clitoris for herself, she wouldn’t have a desperate need for the male; therefore, there had to be some physical reason why only the male’s tendrils could provide that stimulation — and thus I came up with the idea of the covered clitoris, with the inner and outer labia joined to make a “tunnel”, so that only the male’s tendrils could provide the needed stimulation. From there I played on the cultural effects, and the idea that a socially high-ranking family (such as could provide a suitable mate for an ambassador’s son) would be conservative (and patriarchal) enough to not allow the female the mercy of opening up her “tunnels” and exposing her “jewel” so that she could satisfy herself.
It isn't just in K/S that these variations appear; they also show up in het stories. For example in Lois Welling's Spock/OFC story The Displaced (1978), a story that also envisions matching tentacles in female Vulcans: "Now she took a deep slow breath and reached out to run her hand slowly over his chest, down his lean hard muscled abdomen to his genitals, again marveling at the slender tendrils located on either side of his penis. Usually coiled and concealed in the pubic hair, they were now unfurled, and small ripples shuddered down their length.
The Barbed "B'Yadu" Penis
His penis was swollen astonishingly, and seemed to be growing with each thrust. Between lunges he was pulling it out of her, and then pushing back in to what must be an incredible depth. Kirk's eyes focussed, startled, unbelieving, at that massive green-hued phallus. The velvety, trumpet-shaped sheath was, as usual at such times, completely retracted, curled back against his groin. But the rest was not usual at all. The normally quiescent, tender barbs which covered the column to the tip and which always had responded so pleasantly to the touch, were no longer limp and recumbent against the organ but rose at an angle as he watched, and soon were actually bristling, stiff, turning into what looked like spines instead of soft, decorative rickracks of pleasure.
Internal BallsFrom Mirrors of Mind and Flesh:
Pressing inward, Kirk could feel a rounded swelling behind the hot, moist wall... 'I wondered where you had them hidden,' Kirk murmured.... 'What do you call them?' 'The... clinical word is... s'txztiich...' Spock gasped, squirming as the fingers continued to probe the sensitive spot...Kirk laughed softly. It sounded more like a sneeze than a word. 'There is... ahhh... an affectionate term... xaha'si...' Spock whispered, '... from an ancient poem... of Surak's... to the warrior who was his first bondmate.
Massive Vulcan Erection, aka Tower of Jade
Spock was hung as well as any stud pony back on the farm. The human cried out into the night as the enormous cock plunged into him, his legs trembling as they struggled to hold his weight. For an eternity, the Vulcan's cock slid into him. Inch after torturous inch, it opened him, stretching him wide and causing him to beg for mercy for the first time in his life as a slave. .... And still it entered him. Deep. Deeper. Deepest. He felt Spock's balls brush against his own, felt the delicate membranes of his ass stretched until he was certain he would split open. 
The massive Vulcan erection inevitably led to satires like Star Trek: The Lost Episode.But wait, Spock's erection often also had a color! Enter the "tower of jade." In 1999, a fan poked fun at some of her own early fiction:
... we started reading an early story [of mine] and we were in hysterics! I had utilized almost every single “bad” writing technique known to K/S! Things such as using as many adjectives as possible and as many different ones as possible—especially synonyms for the word “big”—you can only imagine to what that kept referring! The thing is that I was so new to writing and so innocent in my first flush of K/S wonderment that I hadn’t a clue as to what might be good, or at least not so purple, writing—and I didn’t really care! I thought “towering jade pole of desire” was perfectly appropriate—it spoke to me; I could visualize it! 
In 2001, a fan commented on a fic:
The scenes [in Sweet Surrender] are mighty hot—especially the ones where Spock administers some fellatio and where he offers himself to his master. If you’ve never thrashed on the carpet after reading a K/S sex scene, you very possibly will now....
[...]The over-all story is kind of “Deanna Gray-lite”, but who cares when you got such mad, passionate, hot, towering-jade-pole-of-desire scenes? 
From Sexuality in K/S Fiction: Anal Intercourse (1985):
Alexis Fagen Black's innovation in "Echoes" (NAKED TIMES 1) is to give Vulcans internal testicles which descent through a hole located where the scrotum would be in humans. Thus Spock has a hermaphroditic quality in this story.in that he can fuck and also be fucked without changing position. Both men and women can be entered through the rear, but among humans only women have frontal genital orifices. So Alexis is giving Spock a psuedo-vagina.
Different Shapes and Sizesiibnf posted a tongue in cheek summary of the various shapes and sizes she encountered over the years:
During the hey day of K/S fan fiction Spock's penis came in a huge array of sizes and shapes. Gayle F was the Queen of The Bells - she had Spock with a penis that came in the shape of five bells, and that will always haunt me. And yet... ribbed... for Kirk's pleasure. Hmm...
The classic fannon that was thoroughly adopted and turned up everywhere was the 'double ridged' penis. That is, Spock's glans had a, er, kind of double echo thing, another set of ridges just underneath. A subtle nod to the alien penis and the fans' love affair with same.
I'm pretty sure there were a load of self-lubricating penises in the stories - because you could so totally get away with that in fandom. And why not? A self-lubricating penis is logical, dammit, Jim!
There was one story (sadly, I never found this one, only heard about it in horrified whispers from friends) where Kirk had been raped and had developed a fear of penises (other people's, one assumes, not his own), but that was just hunky dory as Spock didn't have one. He, instead, had a hundred tiny tentacles that all sort of came together to do the job. How perfect is that? I wish I could find that story, because it's just like mini-hentai! Hundreds of tiny tentacles! Adorable! Although I think it would make giving Spock head an adventure in eating spaghetti. "Hey, Kirk, you want parmesan on that?"
Oh, and there was this really great novel, I forget what it was called, but it was huge, where Spock's nuts were on the inside. In fact, he may have had a couple of sets... no, wait, I remember, his nuts where accessible from the back, like, um, near his kidneys or something, so he really, really enjoyed massages, and then his scrotum just filled up with juice prior to coming. Or something. Anyway, it was hot. Back nuts.My absolute favourite, though, was the extreme alien penis presented by Leslie Fish (Ah, Leslie, your zines are still my sugar bunny comfort fic). Spock's genitals could best be described as a kind of hairy orchid. When he became aroused, the petals unfolded, revealing a studded (with emeralds) green shaft (again, ribbed for Kirk's pleasure!), and two little whippy tentacles that just joyfully joined in the fun. 
From Sexuality in K/S Fiction: Anal Intercourse (1985):
According to Gerry, it is unnecessary for Kirk to reciprocate because the anal passage of a Vulcan lubricates automatically. As is pointed out in ALTERNATIVE 2, this implies that nature approves of Vulcan males being fucked even if Vulcans themselves don't. Vivienne Rivers provides Spock with the Vulcan attribute of a convenient automatically lubricating cock in "Those Who Favour Fire" (THE VOICE 2) . This certainly would improve matters for anyone fucked by a Vulcan.
Spock's penis, when portrayed as an essentially standard male human organ, is often shown as circumcised.One fan writes:
Let's talk cock for just a minute: You got your circumcised, and you got your uncircumcised. Uncircumcised, AKA "intact", "uncut", is the way nature makes 'em. It takes uncounted millions of years for nature to devise something as perfectly delightful as the uncircumcised penis, and only a few seconds with a sharp knife or hunk of broken glass to completely ruin it, OK? The foreskin is not a useless hunk of skin people, it's a very important part of the male organ, that is designed by nature to protect the penis, and facilitate smooth, friction-free fucking... Dare to dream: maybe Vulcans are too smart, too *logical* to ever start circumcising in the first place. Let's assume for a minute that Vulcans are physically, mechanically very similar to humans in the manmeat department. Let's assume that they have a glans, and a shaft, and maybe even visible, hanging testicles. Why in the name of glory would they have two "ridges"? Maybe they wouldn't even have one. Maybe their glans is shaped differently. Maybe they don't even have a "shaft" - maybe the business end of their member is all glans. 
Nothing New Under the Vulcan Suns?
Still, by 2003, some fans felt that the issue of Spock's penis had become settled. Perhaps too settled according to one fan, who comments on this topic in K/S Press #76 (2003):
Anna has some really unique ideas on Vulcan genitalia that I thought were quite fascinating. While there was some initial experimentation with Vulcan genitals in the early days of K/S, nowadays most writers adopt the “fanon” approach of double ridges, and except for this (and some minor variations in the testicles) Vulcan males usually don’t seem too different than human males. Well, Anna has different ideas on the subject, on everything from Vulcan semen (love the idea of the globules), the Vulcan penis and testicles, and even Vulcan anal glands. 
In the following issue of The K/S Press, another fan agreed:
Another fan comments in the essay This Vulcan Penis Problem (early 2000s):Re fannish canon: I agree with Liz, who said last time, that “Double ridges are great, but to be honest I wouldn’t mind a bit of diversity here. I mean, the possibilities are endless.” Ah yes, the possibilities are endless, for K/S is not only fiction, it’s science fiction, and one nice aspect of that is that authors have a lot of latitude when it comes to descriptions of alien cultures and physiology. There is, I must admit, a danger of coming up with some sexual practice that is so alien that readers will find it completely unappealing. But there is also a risk in sticking so slavishly to a few standard possibilities that readers begin to react with a “ho hum” instead of a “yum.” Conflict makes for good reading and cultural differences in sexual practices might make for a bit of particularly interesting conflict in Kirk and Spock’s bedroom. It’s good to be adventurous now and then: if it hadn’t been for Theodore Sturgeon’s willingness to see Vulcans as beings whose sexuality differs from our own, we would never have had pon farr. One person is in danger the other will know about it and come to their rescue: maybe when such a deep bond exists one mate could even help the other heal more quickly when illness and injury occur. Maybe having a death bond makes a pair into super-great parents with super-harmonious, stress-free homes. Maybe the same gene (or genes) that control the ability to form a death bond also affect hormonal levels, increasing fertility. Maybe having a death bond increases the chances of both partners surviving pon farr. 
In the 2011 fanfic, The Squire of Eros, Kirk finally gets a good look at the mystery:I'm going to bounce right off of the ropes and into center ring and just state flat out that I think this "double-ridged" Vulcan penis thing is just plain embarrassing. Something has got to happen, because we can't go on this way....I deplore the fact that so many fan fiction writers agree with such a lock-step mentality about Vulcan penises, when there are so many wonderful options to choose from, and I want you all to start deploring it, too. For mercy's sake people, let's show some imagination! I challenge you Treksmutters to write a sexy story about a Vulcan having sex in a completely new way. Try describing a totally different kind of penis for Spock, and while you are at it, try giving Kirk a foreskin. I double-dare you.
He palmed Spock through the layers of fabric and got a very positive reaction. It was hard to tell through the cloth, but it certainly didn’t feel like anything he had run into before.....This was it. The moment of truth. It turned out that Spock’s penis was like four cords coiled tightly together, about the same size as a human’s, but with a slight taper toward the tip and lacking a glans. He didn’t have balls either; Jim had suspected as much ever since a particularly brutal fight on a planet of waist-high aliens, from which Spock had emerged better off than the rest of them. 
Fan Plays: Dancing Penises -- Starring the Dangly Bits
Fandom's fascination with Spock's penis was celebrated in at least two fan plays. In the 1980s, a skit held at IDICon had fans dressed in "lovingly colored penis suits (one in daring dusky rose, one in ever popular, enticing olive) interacting in a lively dance set to music no less, until both the dance and the penises came to a logical climax." 
See Dancing Penises.
Fan Cakes and PenisesA fan, determined to have a cake with green and pink penises for a con, went in search of a bakery and describes her adventure:
Lo and behold, I see a display ad for ‘[business name redacted], erotic cakes a specialty…’ A pornographic baker? In North Dallas, the buckle of the Bible Belt? I could scarcely believe it… The website sported lots of pre-made penises… but nothing quite what I had in mind. So, taking my courage in my hands, I went to visit the bakery… I talked with the owner of the shop and showed him the picture I wanted him to duplicate on the cake… The baker didn’t even blink an eye. He suggested ringing the cake with pre-made three-inch penises, and I agreed that would be nice touch. ‘I’ll alternate pink and brown,’ he said. ‘No,’ I said. ‘I want green.’ And a ten minute argument ensued. He really wanted to use the ones he’d made up and insisted he couldn’t do green. Finally, he said, exasperated, ‘Lady, we don’t have much call around here for green ones!’ ‘Yes, I know,’ I said. I pointed to the picture on the counter before us, the one of Kirk and Spock making love. ‘However, ‘ stabbing my finger at Spock. ‘He has a green one!’ Well, I won, sort of. He finally agreed to make up a special batch of green penises for me, but he charged me out the whazzo for them, and I think he didn’t use pink ones on the cake, he used brown ones… Since I was in such a whirlwind at KiScon that I didn’t have much of a chance to examine the cake too closely before it was consumed. Oh well, the though was there, and I did fight the good fight for Spock’s penis! 
Vulcan Sexy Fingers
While not genitalia, many fans have speculated on Vulcan fingers and their role in intimacy.
from an unknown fanzine, a parody of "The Hays Code"  -- Vulcan hand and body motions: "A code must be drawn up to limit just how explicit scenes of Vulcan love-making can get and still be shown to Star Trek's impressionable audience. The following are a few suggestions, intended only as a guide until a formal committee can be organized to study the matter."
In Star Trek Reboot Fandom
The focus - or fascination - with Spock's penis has carried forward into the Star Trek Reboot fandom, who often remain unaware of the lengthy discussions from earlier years. Several possibilities have appeared in stories and art. In "Abnormal Growth" by janice lester, Spock seeks medical advice over his penis which is growing beyond normal proportions and somehow winds up with Kirk and McCoy in his bed. Spock has also been given tentacles or a bone. On occasion, in works such as "Long Distance Relationships Are Hard" authors comically exaggerate the proportions or otherness of the much debated penis.
And lastly, Reboot fans have, on a rare occasion, graced Spock's penis with cat-like barbs. 
- Aspects of Vulcan Biology for the Non-Vulcan Student of Anatomy; WebCite, by Greywolf via TrekSmut University, 1996
- This Vulcan Penis Problem (early 2000s?)
- The whole story is in Bjo Trimble's On The Good Ship Enterprise: My 15 Years With Star Trek (Donning, 1983), p. 47.
- On the 1974 album Inside Star Trek, Mark Lenard as Sarek explains to Gene Roddenberry exactly how Spock was conceived and born.
- Smallville would later pick up this torch, although it never got quite as widespread as it had been in TOS
- "Ridges" is incorrect and misleading, but sounds sexier.
- Kirk/Spock Fanfiction Archive - Gayle F, 13 March 2009. (Accessed 30 June 2011)
- She's probably referring to Lovecraft's story "The Dunwich Horror", in which a monstrous half-human creature is described: "Below the waist... all human resemblance left off and sheer phantasy began... from the abdomen a score of long greenish-grey tentacles with red sucking mouths protruded limply."
- from Media Fandom Oral History Project Interview with Gayle F and Caren P <2013)
- from The K/S Zine: The Time of the Beginning 1976-1985
- Poses by Leslie Fish, via the Foresmutters Project archive. Accessed 27 October 2008.
- Kathy Resch, Archived ASCEM message, 5 February 2008, accessed 27 October 2008.
- Aspects of Vulcan Biology for the Non-Vulcan Student of Anatomy, by Greywolf the Wanderer, a TrekSmut University lecture. Accessed 27 October 2008. Backup website link [backup website link here
- Lois Welling. The Displaced. Accessed 5 Aug 2010
- from the story "Psychic Storm", published in Naked Times #27 by Alexis Fegan Black (1991)
- from The K/S Press #40 (December 1999)
- from The K/S Press #60 (August 2001)
- ~iibnf "...made a post today with a throw away comment about Spock and his amazing metamorphosing penis"; dated Feb 26, 2007.
- "His hand followed the wiry trail of body hair over one nipple and down swiftly to the Vulcan's penis. Oily -- how very sensible -- unaroused apparently but perhaps that was how it was for Vulcans."
- So much for the running gag among members of S.T.A.R. San Diego that all Vulcans are Jewish.
- from This Vulcan Penis Problem
- K/S Press issue #76, taken from a review of Trusting the Spirit.
- from "Fanon AND genitalia," K/S Press #77 (2003).
- The Squire of Eros by aldora89, dated Feb 19, 2011.
- See Dancing Penises
- See Escapade/Escapade_1995.
- from The K/S Press #59 (July 2001)
- "The Motion Picture Production Code was the set of industry moral guidelines that was applied to most United States motion pictures released by major studios from 1930 to 1968. It is also popularly, albeit inaccurately, known as the Hays Code..." -- see more at Wikipedia
- "Abnormal Growth" by janice_lester, dated November 15, 2010.
- cannedebonbon. Art: I'm so sorry about this. Post in kirkspock LJ comm, 2010-04-06
- "I recently read Chase820's fabulous Reboot story "Secret Vulcan Mating Rituals" (still a WIP, alas), in which Spock's penis is barbed, like a cat's, and I've been wondering whether that appears in TOS fanfic as well. I've seen Vulcans made into descendants of felines in TOS fanfic several times, but I can't recall any TOS examples for cat-like penis details going along with this. I've seen many instances of the notorious double ridges, and I have seen a couple of more alien configurations, like tentacles and such for Spock's genitalia in TOS fic now and then, but I can't think of any cat-like penises. in alien physiology, posted by ratcreature, dated Feb 18, 2010.