1550s (n.), "native or inhabitant of Prussia;" 1560s (adj.), "of or pertaining to Prussia;" from Prussia + -an. In reference to the language of the earlier inhabitants of (East) Prussia, which was closely related to Lithuanian, by 1888. It was spoken between the lower Vistula and the Niemen and was extinct by the end of 17c. Prussian blue pigment (1724) came to English from French bleu de Prusse, so called for being discovered in Berlin, the Prussian capital.
All in all, it seems that Prussian blue was synthesised for the first time around 1706 by the Swiss immigrant Johann Jacob Diesbach in Berlin. [Jens Bartoll and Bärbel Jackisch, "Prussian Blue: A Chronology of the Early Years," in Zeitschrift für Kunsttechnologie und Konservierung 24, No. 1, 2010]
Early German sources refer to it as Preußisches Ultra-Marin and berliner blau. Prussic acid (1790), is from French acide prussique, so called in reference to Prussian blue pigment, to which it is chemically related.