There is a book I really loves that expose really well the mindset we had at that time: Zen of assembly programming, by Michael Abrash. As far as I know reading it is the best way to really understand how programmers achieved wonders at that time.
In the eighties with fellow programmers I wrote a few games for 8 bits machines. Not the best games around, but we used the same kind of tricks as others. One I was really proud of was one of the first First Person True 3D (using wire view, surfaces came a few years later) real time adventure game running on CPC464. Not much chance anybody heard of it as it was not a hit, only selled a few thousands.
What was amazing was the 3D engine. To make it both fast and small we had to rewrite all 3D computing math using power of two friendly arithmetics for angles (ie: a full circle was 256 "binary degrees"). Function calls used bit tailored parameter passing through registers, and so on. It also used automodifying code to transmit parameters. The method may appears mad nowaday, but if it's small enough you can store a value inside the assembly opcode used to load a "constant". Really it makes that constant a variable it's faster and has smaller footprint.
We also redefined some basic things like alphabetic order to get better huffman-like compression for the game strings. An external program was building the most efficient possible alphabet to store messages.
As others said we also managed memory in a very aggressive way : parts of code only needed at loading time became room for datas afterward, parts of screen were also used to store programs of data.
Lots of such tricks.
