Avec une minuscule ou une majuscule selon l'emploi.
Avec majuscule.Le Palais de Justice, ou, absolument, le Palais, pour l'édifice parisien.
remarque
Ce sont des majuscules d'usage. Mais on écrit avec des minuscules palais de justice pour l'édifice d'une ville quelconque : le palais de justice de Bordeaux.
Avec majuscule pour certains édifices parisiens : le Grand Palais, le Petit Palais, le Palais-Royal (avec trait d'union).
Avec p minuscule (et majuscule au nom qui suit) : le palais Bourbon, le palais Garnier, le palais des Glaces, le palais d'Hiver, le palais des Papes.
remarque
C'est le nom qui suit qui caractérise le nom propre de l'édifice ; il prend la majuscule.
Avec p majuscule quand on parle non de l'édifice, mais de l'ensemble des personnes qui y exercent une activité : le Palais (magistrats, avocats, etc.) ; tout le Palais était venu écouter la plaidoirie de maître X. - Le Palais-Bourbon = l'Assemblée nationale, l'ensemble des députés. Le Palais-Bourbon doit examiner le texte gouvernemental.