См. в «Письмовнике»: Особенности склонения фамилий и личных имен.
В орфографических словарях зафиксировано написание с прописными буквами, склонение второй части необходимо, например: исполнила партию Царевны Лебеди, думаю о Царевне Лебеди, идет рядом с Царевной Лебедью.
Это сочетание пишется раздельно, склоняются обе части: Царевны Лебеди, Царевне Лебеди и т. д. Обратите внимание: в этом сочетании Лебедь женского рода.