They didn't work like modern interpreters, which basically compile the program into bytecode and then interpret the bytecode. They would do simple very simple parsing of the program, mostly just tokenising it, and then more or less execute each Basic statement directly. (Sinclair Basic's wacky keyword-at-a-time entry system meant they didn't need to ship a tokeniser.)
So:
10 LET I = 10
20 LET I = I + 1
30 GOTO 10
The program counter would point at the start of line 10; the interpreter would see LET (mandatory in Sinclair Basic) and know a variable name was next; it'd read that; it'd read the equals sign; then it would read the expression and evaluate it on the fly. Then the program counter would be pointing at the end of line 10, so it just advances over the line number, and it's ready for line 20. etc, etc.
Line 30 would read the GOTO, then read the line number, then reset the program counter to the beginning of the program and scan through looking at line number headers until it found the right one. Yes, O(n). Yes, you put most used subroutines at the beginning of the program for speed.
So the entire run-time state is a program counter, a couple of fixed-size stacks for FOR...NEXT and GOSUB...RETURN, and your variables. I've no idea how Sinclair Basic stored them, but BBC Basic used a hash table that was immediately after the end of your program. Strings were a problem because they could change size; Commodore Basic had the world's slowest garbage collector. BBC Basic just fragmented and ran out of space. I don't know how Sinclair Basic handled it.
If you're interested, the entire ROM is disassembled here: http://www.wearmouth.demon.co.uk/zx81.htm