Lookup tables have been mentioned in comments. There are two approaches.
Fast
Create a 256 bytes long table, with every next value the square root of the corresponding index. This is fast since you use the argument as index to access the right value directly. Drawback is that it needs a long table, with lots of duplicate values.
Compact
As said, an 8-bit integer can only have values 0 through 255, and the corresponding square roots are 0 through 16 (rounded). Construct a 16 entry table (zero-based) with the n-th entry the maximum value for the argument for which the square root is n. Table would look like this:
0
2
6
12
20
etc.
You walk through the table and stop when you encounter a value greater than or equal to your argument. Example: square root of 18
set index to 0
value[0] = 0, is less than 18, go to the next entry
value[1] = 2, is less than 18, go to the next entry
value[2] = 6, is less than 18, go to the next entry
value[3] = 12, is less than 18, go to the next entry
value[4] = 20, is greater than or equal to 18, so sqrt(18) = 4
While the fast lookup table has a fixed execution time (just one lookup), here the execution time is longer for higher value arguments.
For both methods goes that, by choosing different values for the table, you can select between a rounded or a truncated value for the square root.
From the older machines that I have looked at, often a clock was kept running via a small cell battery. And the time on that clock at start up was checked and used for various calculations. I'll try to dig up a concrete example when I get home from work!
Edit:
One common way of implementing this was through the classic 555 timer chip, circia 1971 (Either the IC or designing one with electronic components) An explanation of the chip can be found here:
http://en.wikipedia.org/wiki/555_timer_IC
This chip can typically be found in any hobbyists toolbox, but how do we use this chip to generate random numbers? The short answer is that we cannot, we must use this in conjunction with other coutning circuits etc. While today these can be found in convenient IC packages, they can be recreated with common components. I tried to prepare a good example, but managed to find a much better one online! An example of such can be found/explained here:
http://www.engineersgarage.com/electronic-circuits/random-number-generator-using-7-segment-display
Hope this helps! :)
Best Answer
See this article
Uncertain Circuits: When transistor 1 and transistor 2 are switched on, a coupled pair of inverters force Node A and Node B into the same state [left]. When the clock pulse rises [yellow, right], these transistors are turned off. Initially the output of both inverters falls into an indeterminate state, but random thermal noise within the inverters soon jostles one node into the logical 1 state and the other goes to logical 0.
Also see the white paper (Respawned Fluff note: This is for an older Intel method, using two free-running oscillators, not the one described above.)