"Propaganda" simply meant the propagation of information. The terms goes back to the 17th century, when the Catholic Church established the "Sacra Congregatio de Propaganda Fide" (Sacred Congregation for Spreading the Faith), or "Propaganda Fide" for short, a missionary organisation for the propagation of the Catholic faith. From this, "propaganda" was being used to describe the secular dissemination of information by the end of the 18th century. "Propaganda" started acquiring some negative connotations already during the 19th century (in the same way that "advertising" and "marketing" can have negative meaning), but especially in an official context was still a neutral term.

Thus, a "Ministry of Propaganda" was simply a "Ministry of Communication", or "Public Relations", or "Information" (a "Ministry of Communication" might also just manage national telecommunications infrastructure, with no public relations or propaganda role). Such ministries often also include broader cultural activities, so a "Ministry of Propaganda and Culture" would not have been unusual. After WWI, "propaganda" acquired a stronger negative meaning, especially in the English language, and some ministries were renamed. For example, the Irish Republic's "Department of Propaganda" was renamed the "Department of Publicity" in 1921. Outside the Anglosphere, "propaganda" remained in official names for longer, such as the Soviet "Department for Agitation and Propaganda" AKA "Agitprop", the official producer and supervisor of agitprop for the Communist Party, and the Nazi "Ministry of Public Enlightenment and Propaganda". Fascist Italy's version began as a "Press Office" in 1922, becoming the "Secretariat for Press and Propaganda" in 1935, and then the "Ministry for Press and Propaganda" in 1935, and finally the "Ministry of Popular Culture" in 1937.

Soviet and Nazi use further tarnished the image of the term "propaganda" in the English language, and further name changes occurred. The Chinese "Chinese Communist Party Central Committee Propaganda Department" changed from a "Propaganda Department" to a "Publicity Department" in 1998, as far as its official English name goes, while keeping the same Chinese name "中国共产党中央委员会宣传部"; "宣传部" can be fairly translated as either "propaganda department" or "publicity" department, and "宣传" can have a negative meaning in Chinese (of course not when it refers to official 宣传!). The name of "Propaganda Fide" was changed in 1967, top "Congregatio pro Gentium Evangelizatione" ("Congregation for the Evangelization of Peoples"). Even the North Korean "선전선동부", fairly and formerly translated into English as "Propaganda and Agitation Department" is official the "Publicity and Information Department".

In some languages, "propaganda" is still used broadly, with no more negative meaning than the English "advertising".

EDIT: There have been many followup questions about other terms such as "scheme". "spin" and "cabal". I don't have answers for these. There are many interesting rabbit holes about the history of the usage of many words, and I hope that the askers of these questions, or other readers, will have fun exploring these rabbit holes!