Well, my political science professors say that a nation has to have sovereignty and clear defined borders. It also has to have a defined population, the ability to enter into agreements with other nations as equals, and a single government. The best examples would be the nations that we see every day, the US, the UK, Russia, China, and Japan.
For sovereignty, I would think that Yukari oversees most of the Gensokyo, with the Celestials administering their little patch of heaven, Yuyuko in the Netherworld, the Yama at the ministry, and Satori watching over hell. Remiu would be the enforcing authority, if she's not feeling lazy that day. The barrier would work as defined borders, if magical boundaries can count. The defined population would be everyone within the barrier, so that counts. Since Gensokyo is hidden from the world at large, it can't really enter into agreements with other nations and can't be recognized by other nations as an equal. The single government is a bit trickier, with all of the factions around. There could be an argument that Yukari is the de facto lead, but I haven't seen that many instances of her taking charge outside of the first Lunar-Genso war. I could be wrong about that.
Outside of the established states that everyone recognizes, it's a bit tricky to pin down what exactly is a state without outside views. Some of the Native American tribes are recognized as sovereign states by the US government, but that's a complicated arrangement (just like everything with government). In my eyes, Gensokyo qualifies more as a nation-state, like the Vatican. It's self contained, somewhat homogenous (becoming less so due to the religious arc introducing different religions ) and stable.
I could be wrong though.
