While 괜찮다 and 귀찮다 may not be related in meaning, they both share the common ending -찮다 and have origins which are simple enough to explain that I have included both in one post.
As every learner of Korean quickly realizes, 괜찮다 is an extremely useful word which can be applied in a variety of situations. But where exactly does it come from? You may have intuitively guessed that it is the contraction of a negative ending, which is correct: -찮다 is simply a contraction of -치 (cf. "-지 않다") + 않다 (않다 -> 아니하다 "to not be"). "괜" is a contracted form of the noun 관계 (關係) "relation, connection." Written out, the word's entire original form would be: "관계하지 아니하다," meaning "to not be concerned/ relevant/ matter." Hence the meaning "it is okay/ alright" (i.e. "it does not matter, it is of no concern").
Now that you know that -찮다 is a contraction of a negative verb ending, we can focus on the initial -귀 in 귀찮다. 귀 is from the Chinese character 貴 ("귀"), meaning "precious, valuable." Thus, the two parts 귀 + 찮다 together mean "not precious/ valuable." When something annoys you or is not worth your time and effort (a general sense of "troublesome, tiresome"), it is "not valuable, important, precious."
As you can see, the origins of both words are remarkably simple and intuitive, and many learners will likely be able to guess them if they already know the related words "관계" and "귀하다."
백문식. 우리말 어원 사전. 1st ed. 서울: 도서출판 박이정, 2014. Print.