Yes. Like the random functions in most programming languages, it's not actually generating real random numbers. Instead, it does various operations on each number to get the next one, and these operations are complicated enough that the results appear random. Because each number is only based on the one before it, you'll always get the same sequence by default. To "seed" the sequence, you can call the randomSeed() function in your setup(). You can try passing it the value of an unconnected analog input (e.g. randomSeed(analogRead(0))), which gives a sort of random value. Or you can try to generate random data some other way - e.g. if you've got some pushbuttons connected to your Arduino, you could call randomSeed(millis()) when one of the buttons gets pressed. Or you could send a random byte from the computer over the serial connection.
The Make blog actually had a nice link to a proper random number generator recently: http://www.makezine.com/blog/archive/2007/09/orb_open_random_bit_gener.html