The full scientific and technological story is a long and complicated one (I'd recommend Rhodes' The Making of the Atomic Bomb if you want to get a deep understanding of the science even as a layman), but the basics are that there had been work probing the structure of the atom from the 19th century until the 1930s that was increasingly getting more and more sophisticated. In late 1938, Otto Hahn and his team unexpectedly found evidence that uranium atoms could be split with neutrons (a subatomic particle that had been discovered in 1932). By early 1939 every physicist in the world was aware of this — it was huge, interesting scientific news. But by itself this did not mean a weapon was possible, unless the reactions could be chained together, so that one split atom would split two more atoms which would split two more atoms and so on, so that a lot of atoms could be split very quickly. There were several scientists to whom it occurred the idea that this might happen (Leo Szilard was probably the first, but there were others who intuited the possibility). Verifying this took some months, but by late spring 1939 it was clear that atomic bombs were potentially possible.

This didn't mean that they would be easy to make, or even could be made. There were an exceedingly large list of "unknowns" and many reasons to suspect it was very difficult (it was discovered early on that only one very rare type of uranium — the isotope uranium-235 — would split this way; 99% of uranium in the world is another type, uranium-238, which actively inhibits reactions; splitting the uranium-235 from the uranium-238 was a difficult technical endeavor). So there was no mad rush to make these weapons. But there was a push by scientists in many countries (the US, UK, Germany, France, the USSR, and Japan) to have their governments fund investigations into whether it was possible.

It was the result of these investigations, and perhaps an unwarranted optimism about how easy it would be, that led the US to decide to pursue a full-fledged bomb-production program starting in 1942. This was the Manhattan Project, and resulted in three atomic bombs ready for use in the summer of 1945. No other nation made this decision to produce atomic bombs during the war. It turned out to be very difficult indeed, and the US barely pulled it off despite pouring essentially unlimited resources into it, and giving it the top priority of all wartime projects. It cost about 1% of the US total war effort, and employed about 1% of the entire US civilian labor force — a huge expenditure for a single scientific project. If you'd like more detail on how they did it, you can read an article I wrote about the Manhattan Project here, which is basically a "what I think people ought to know about the Manhattan Project" encyclopedia entry (aimed at scholars and interested laymen).

So to summarize the first part of your question, the answer is: after the discovery of nuclear fission, many scientists, globally, realized that you might be able to use this new scientific phenomena in a weapon. But it took a lot of research to confirm this was true, and after that it took a lot of industrial/scientific effort to actually make it happen.

---

To answer your second question, Truman was definitely not the first politician to know about this work. In fact, he was not told about it until April 1945, after Roosevelt had died. Which is a rather remarkable thing by itself!

Winston Churchill was probably the first head of state to talk to a scientific advisor about nuclear fission; he was very interested in the idea of nuclear energy (well before the discovery of fission) and had a close relationship with Frederick Lindemann, a physicist, who followed such matters. Lindemann told Churchill in August 1939 that nuclear weapons were probably not feasible — maybe the first recorded instance we have of a head of state talking about this matter. Churchill would stay interested in the topic as it developed, and would eventually get permission to allow UK scientists to work on the US project.

US President Franklin Roosevelt was formally briefed on the matter in October 1939. He had been given a letter written by Albert Einstein (with the aforementioned Leo Szilard helping) telling him about the discovery of fission and encouraging him to put government resources into the work.

Adolf Hitler was briefed on it in late 1940, by the Minister of Posts, Wilhelm Ohnesorge, who had been given a presentation on the topic by the scientist Manfred von Ardenne.

I don't remember exactly when Stalin was personally brought in on the fission issue. Definitely by 1942. But probably earlier; the Soviet scientists had begun working on the same sorts of investigations that were being done elsewhere in 1939-1940.

I have no idea whether Emperor Hirohito had been told about the possibility; it's an interesting question (translation: I'll dig around and see what I can find, when I get the time). Slight update: it's not clear to me that Hirohito was ever briefed on the small Japanese fission program. Prime Minister Tojo, however, did know about it by at least 1942 (after the Battle of Midway, they did a review of their "wonder weapon" efforts).

So as you can see, Truman was actually one of the last major heads of state to know about such a thing.

There were of course lower-level politicians who were aware of this work in the US and elsewhere (e.g., the US Secretary of War, Henry Stimson, followed the work very closely; in Germany, their equivalent person was Albert Speer, and he was informed of German work on the topic; in the USSR, the work was overseen by Lavrenty Beria).