How was early randomness generated?

The one-word answer to your question is "badly".

The way to create random numbers quickly is via a Pseudorandom number generator (PRNG). That Wikipedia page gives the history of PRNGs and in particular notes that linear congruential generators are/were common, with quite a few failings including periodicity (i.e. it cycles through the same sequence of values), poor distribution, predictability, and quite a few other faults that make them poor choices for use in cryptography. That page also describes linear-feedback shift registers but I don't recall them being used in the BASICs of my youth.

The first decent PRNG is the Mersenne Twister, which was invented in 1997. It requires 2.5kiB of RAM to store its state, and is relatively computationally intensive, so it would be ludicrous to provide it as the standard random number source of a BASIC running on a machine with only a few tens of kilobytes of RAM and a slow CPU even if the algorithm had been known at the time.

Cryptographically-secure random numbers need the aid of a hardware device that contains true randomness, such as interrupt timings from I/O devices, or even a dedicated quantum noise source. Again, older machines tended not to have much in the way of interrupt-driven I/O, commonly using a vertical blank interrupt to trigger a polling process instead.

For a concrete example, look at the source of the Sinclair ZX Spectrum's RND function. In case that link goes bad, I'll also summarise it. There is a 16 bit system variable SEED which unsurprisingly contains the current random number seed. When you call RND, it computes (SEED+1)*75 mod 65537 - 1 which it stores in SEED, and returns SEED / 65536, i.e. a value in the range [0, 1).

Because SEED is just 16 bits, it's clear that this PRNG can't have more than 65,536 possible states. Mathematical analysis of the function it uses to generate the next SEED will show that it has exactly 65,536 states, and thus will repeat and generate the same values after that many calls. It's alright for deciding where to put aliens on the screen, but I wouldn't trust my online banking to it...

Interesting question. After all, it's the main job of a computer to come up with deterministic results, which is pretty much the opposite of pure randomness.

In reality, coming up with a series of non-deterministic numbers from a digital circuit only is considered technically impossible. Modern computers use "known noise" in their peripheral devices or even dedicated noise generator circuits to seed their random number generator. Older home computers didn't really have that much periphery to choose from so used "close-to random" values as a seed like video flyback counters or "time since switched on".

Once you have a (more or less random) seed (initial value), a simple RNG (Random Number Generator) typically consists of an LFSR (linear feedback shift register) that runs the seed through a binary polynom, generating a new value from the previous one that "looks" random (picture source: Wikipedia) (Today's computers tend to use much more sophisticated RNGs)

Note what "looks like hardware" in the picture can easily be reproduced by software in a computer. A random number would then just be the current value of that 8 bit register. A new random value is being generated on every fetch by shifting the old value one bit and feeding back the "carry" and bit positions determined by the chosen polynom into the lowest bit.

In pseudocode, an RNG looks somewhat like this (implements the above picture):

carry = (x & $80) != 0 
oldx = x
x = x >> 1
x |= (carry + (oldx & $04) > 0 + (oldx & $10) > 0 + (oldx & $20) > 0) != 0

In reality, most of the RNGs did, different from the example, normally use 16-bit shift registers and the polynoms might look different.

The initial state i.e. the seed of the shift register is normally set by the RANDOMIZE (or similar) Basic keyword. This might be the most misunderstood and misused basic keyword ever - It somehow seems to imply to make the RNG "more random" but instead does the exact opposite - By seeding the RNG with a constant number, you can make different computers with the same BASIC produce the exact same sequence of random numbers. Using this technique you can easily create encryption programs that can only be decrypted by the same RNG using the initial seed as a key (i.e. cyphers produced by the Commodore C64 that can only be deciphered by a C64). I also remember a Basic program I once wrote for the Sinclair QL that calculated the value of PI by simulating rainfall (random coordinates) onto a circle in a square and determining whether the raindrop fell into the circle.

A "cryptographically secure" source of a seed for the RNG is not known to me from early computers - At least not of home computers. After all, proper encryption which is the main use for RNGs was not necessary on a non-networked computer (most of the early computers were) as long as you had a proper door in front of it. Only the development of larger networks and the internet made encryption really necessary - before that time, you could simply rely on physically securing computers.

Some games used the contents of ROM, or a subset of it, starting from a timer-fed address and looping. Because of the limited amount of space available, ROMs tended to be written to be very compact though you will sometimes get blocks of zeroes or repeating data, which is why a subset is often used. Other games on the Z80 CPU used the bottom 7 bits of the R register, which is actually there to provide a refresh signal for DRAMs, and increases by 1 every instruction fetch. This is often random enough for game purposes though there's a strong correlation between close reads. There wasn't much call for encryption-strength randomness on a computer not attached to a network. Some of the game loaders used scrambling and tricks to protect their games from being cracked or modified, but this decryption had to actually be deterministic to produce the same results every time.

The Commodore 64 had a built-in audio processor, called the SID chip. This chip would generate sounds based on (among other things) a frequency (e.g. 440 Hz) and a wave shape (square, sawtooth, etc.). One of the options was to generate "white noise", which is basically a random series of volumes. Now the fun bit about this is that you could read a snapshot of the current volume from one of the SID registers, which in white noise mode, was an essentially random value from 0-255. This technique was commonly used on this platform. Even, if I recall correctly, in BASIC programs, though BASIC had a built-in random function.

Now, I'm pretty sure this randomness was generated in hardware, which probably means it was closer to true randomness than the software techniques described in the other answers. Or it may have been a variant of the circuit described in tofro's answer. In any case, there may well have been biases in the distribution or other features in the values generated that would make these values weak for cryptography.

On some games like "Super Mario 64", the randomness was determined by simply XORing the value whenever it's called (technical detail can be found here). This allowed it to be exploited, especially on places where it's never called naturally, like Peach's castle, but by doing moves that generate dust (which calls the RNG function itself), it can be exploited. One example of such a glitch can be seen here.

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin — John von Neumann

The method that RAND used to calculate their A Million Random Digits with 100,000 Normal Deviates is described in this brief paper: History of RAND's Random Digits: Summary from 1949. In summary, the gated output of a gas-filled thermionic valve (such as a 6D4 Thyratron, well known to produce noise under certain configurations) was used to increment a five bit counter. Once per second the noise signal was interrupted and the counter read through a BCD converter to produce decimal digits. As the counter would overflow more than 3000 times per second and was fed by pulses with very fast random timing, the results passed all randomness tests available at the time. A similar gas-discharge valve noise system was used in the UK's random draw generator (ERNIE) for premium bonds.

Alan Turing identified a very early need for true random numbers in computing, and his design for the never-built Automatic Computing Engine (ACE) (1945-6) was to include valve-based noise generators. These were to be used to assist in Monte Carlo simulations, as developed by Ulam for nuclear fission modelling.

(I seem to remember reading the statement about Turing and RNGs in George Dyson's book Turing's Cathedral, but I no longer have a copy to check.)

Many early systems used the RANDU PRNG (seed = seed*65539 mod 2³¹; the initial seed must be an odd number) which happened to be not very random. If it is used to generate 3D coordinates, the resulting points are positioned on a few fixed planes. Another visualization of this in an implementation of BASIC on Elektronika BK-0010 is here.

Testing for RANDU can be done by drawing a few thousands of pixels with

PSET (RND*width,RND*height),RND*numcols

and observing the diagonal stripe pattern.