Nichelle Nichols on naming Uhura and on getting the part (transcribed by me from a making-of segment on the ST:TOS Blu-ray set, at the end of season 2):
They hadn't written Uhura. It was taken from a book I was reading, which was this marvelous treatise on Africa called Uhuru, which is the Swahili word for freedom. Later, when I got the part, [there] was no part to read. So I read the part of Mr. Spock. I said, "Well, could Spock be a woman?"
[They] told me [...] Leonard Nimoy was already playing [Spock], and it's Mister Spock. I said, "Well could it be?" and they said, "Yeah, but Leonard Nimoy wouldn't like it." So still I read for it, and they explained to me what kind of character [Spock] was, and I brought those given circumstances to the reading. And it was a nice long scene, it was Spock, Kirk, and Bones, so here I was with these guys—somebody else of course read [Kirk's and McCoy's parts]—and when I finished, there was silence, and finally someone said, "Why don't we have Penny call downstairs and see if Leonard Nimoy has signed his contract yet." [Laughs.] And that was their charming way of telling me I was going to play [a] character [on the show].
So Gene, for celebration, and the director and a couple others, took me to lunch, and he said, "I want to talk to you about that book," which we had been chatting about. He said, "I like that word 'uhuru,' and I've been wondering what to make this character. And I'm thinking why not from the United States of Africa?" I said, "I think that's beautiful." He said, "But I want to use that name Uhuru, but it's a little hard, it's a little—" And I said, "Well, instead of Uhuru, why don't we make it Uhura?" He said, "I love it." I said, "Which will it be, last name or first name?" and Gene said, "Let's hold off on that, I'm not sure, it's gotta be the right thing, but right now you're Uhura," and I said, "All right, I love that."
And it wasn't until [some time] later that a writer writing the history of Star Trek, the original series, called Gene and said, "What is Uhura's—is that a first or last name?" and Gene said, "We never decided." And [the writer] said, "Well, because it's [based on] 'uhuru,' freedom, what about that being the last name, because I think I have a beautiful Swahili name for her first name." Gene said, "What is it?" He said, "Nyota." Gene said, "That's beautiful. What does it mean?" He said, "It means star." Gene [...] could have said, "Yes, that's beautiful, Nyota Uhura," [but instead he] said, "Well, Nichelle created the character and she gave it the name; I think you'd better call her and ask permission. Because if she doesn't like it, I'm not gonna give you permission." So [the writer] calls me, tells me, and I said, "What name did you have in mind?" He said, "Nyota." I said, "That's beautiful, what does it mean?" He said, "Star." And I thought, a star of freedom, free-floating star, and I said, "Perfect."
(See also a slightly different telling of the same trying-out-for-Spock story.)