Random Number Generators(RNGs) are really generating pseudorandom numbers, since it's impossible to actually generate a TRULY random number. The only really truly random things are acts of God, like lightning.
This wikipedia article might be able to help you out in the explanation: http://en.wikipedia.org/wiki/Random_number_generators
From what I understand, there are basically two parts of an RNG: the seed, and then the random number chosen from that seed. When you seed the RNG, you are giving it an equivalent to a starting point. That starting point then has a bunch of numbers that are "inside" of it that the program chooses from. In PHP, you can use srand() to "shuffle" the seeds, so you almost always get a different answer. You can then use rand(min, max) to go into the seed and choose a number between the min and the max, inclusive.
WARNING, POSSIBLE CHEESY ANALOGY AHEAD!
Think of each 'seed' as an ice chest, and then the random numbers as ice cubes. Let's say you have 1000 ice chests and each chest has 1000 ice cubes inside. At the county fair, they'll choose an ice chest to start using for drinks, and they can only use one ice cube. However, they only need ice cubes bigger than 1 cubic inch. So they'll choose a chest at random between those 1000 chests, and then they'll choose an ice cube inside that chest at random. If it works for the size they want, they use it. If it's not, they put it back in the chest with the others. If they want to make it a little more fun they change chests beforehand for total obliviousness, if you will!
As for how PHP actually physically chooses the seed and the random number, I don't have enough knowledge for that(which is probably what you were wondering the most about!). I wouldn't try and redo the rand() function; for most web based applications that you'll make, rand() should suffice for any random number you'll need.
Also check out linear congruential generators, this might be more of what you're looking for if you want the dirty details: http://en.wikipedia.org/wiki/Linear_congruential_generator
Hope this helps!
Sign is on a good track, but his algorithm is wrong. It is not much random. It is actually pretty hard to create random like this. I was playing around with this and everything I tried created obvious patterns when printed in 2D. In the end I manged to create an algorithm that doesn't create any eye-visible patterns. I looked for inspiration in existing random algorithms.
public static uint bitRotate(uint x)
{
const int bits = 16;
return (x << bits) | (x >> (32 - bits));
}
public static uint getXYNoise(int x, int y)
{
UInt32 num = seed;
for (uint i = 0; i < 16; i++)
{
num = num * 541 + (uint)x;
num = bitRotate(num);
num = num * 809 + (uint)y;
num = bitRotate(num);
num = num * 673 + (uint)i;
num = bitRotate(num);
}
return num % 4;
}
When this algorithm is used to render a 4-shades of gray image, it creates this:
For comparison, the Random algorithm creates this pattern:
And Sign's algorithm too has patterns: 
Best Answer
First, you use Normal distribution to generate population of each village. This should give you number that is pretty close to total population. To get exact population, just add or remove the difference evenly across all villages.
The problem of this algorithm is that there is some probability of generating negative population. But that heavily depends on parameters. For parameters from your example, the probability is extremely slim. But for parameters (10000, 100, 50), the probability is there.
While this code doesn't give precise number. It deviates +-10 which is fine.