I just finished up the last quest on Korriban, and my companion, Khem Val keeps saying, "I want to speak with you."
So... I right click him, and he says: "I want to speak with you."
So, I'm at a loss. How do I speak with the big lug?
You'll need to find some privacy before your companion will open up to you.
In other words: once you get your own ship, speak to them there.
One exception to the cantina rule is the small cantina in the Senate Tower on Coruscant. My companion refused to talk to me there, so I had to take him to the other Cantina, the one in the Market Sector. Once they are in the right area a quest marker will appear over their head and you can right click to start the conversation.