First, you have to have "close" relations with the particular race. You can see what's affecting your relations with a race by going to "reports" in the "foreign relations" section. There will be +'s and -'s based upon things like "shared borders" (-), "ethical allignment" (+ or -), "militaristic" (I've always seen this as -, but does anyone know if it refers to YOU being militaristic or the foreign race being so?), "trading" (+), and "historic relationship" (+) or "historic animosity" (-). There are more possible factors, but this is what I can think up right now.
Sometimes you just won't be able to get relations to close no matter how hard you try, other times you'll find yourself close with someone when you haven't tried at all. But it's not random, as far as I know.
Edit -- Oh, and you have to have the tech "alliances," obviously.