What is the origin of the WASD key scheme?

Wikipedia's article on arrow keys covers some of the history of WASD:

The scheme wasn't popularized until competitive play in Quake and subsequently QuakeWorld made clear its advantages over the older arrow key configurations.

Competitive Quake play only popularised the layout though, as it wasn't the first time they were used:

In the same year that Castle Wolfenstein was released, 1981, the game Wizardry used the AWD keys for movement in a 3D dungeon. Both the programmers of Castle Wolfenstein and Wizardry were users of the earlier PLATO system where the game Moria used the AWD keys.

So they were popularised by Quake and the FPSs that followed and made it default, but they'd been around as a control scheme for a while already.

WASD keys are the left most keys which form an arrow shape, allowing the left hand to control movement (and still allow the thumb to reach the spacebar). The right hand is free to use the mouse. This setup is for right handed users who use the mouse with their dominant hand.

One of the reasons is the more frequent use of the mouse in games, and since most people are right-handed, it makes sense to control movement with the left one. And since putting the left hand on the arrow keys would put it in an awkward position, why not keeping it on the left side?

Another possible reason might be the need for more keys to use around the one hand on the keyboard.