It sounds like it ought to be cognate with French colombe and Latin columba, but apparently not.
And "голубой" is the word for "sky blue", although doves can be of different colors )))
Btw I have not recalled the word "dove". I wrote "pigeon" instead.
The Polish word for dove is "gołąb", pronounced - "gowomb". Looks like an intermediate version between French and Russian. (And this l -> w change is only last years tendency)
Actually, "голубь" and "голубой" do come from the same source. According to some researches the bird's name comes from the colour (as the feathers around their neck are somewhat blue), the others (researches, not feathers)) claim that it's actually the opposite - the colour comes from the bird, and the "голубь" itself comes from the lithuanian gulbė̃ (a swan), or e.g. polish - see below) But anyway both words have one origin, so when you doubt how to spell "гАлубой" or "гОлубой" you can think of a dove where the О is under stress.
oh haha sorry, i misunderstood=) actually there are some sources that say those are relative words too=)