Karateka didn't use any of the C64's advanced features (hardware scrolling, sprites) as far as I know, being a game that originated on the Apple II. It was still very impressive. I wonder which C64 game was the first to have smooth parallax scrolling (at 50/60Hz).
The technique of pre-shifting was used very widely, even on consoles with some form of hardware assistance (Sonic 3 uses pre-shifted images to gain an extra parallax layer in some places, like the Launch Base Zone background, in addition to the two hardware tile layers and single sprite layer, which could be combined in interesting ways via priority bits). Many Amiga games would also dedicate two sprites to generating a parallax layer (as the Agnus chip's "copper" could rewrite sprite registers mid-scanline, two sprites would be sufficient to cover the whole width of the screen via updating the image pointers on the fly, which was really the endgame of the idea of "racing the beam", dedicating a piece of compute logic towards updating registers at extremely high speed)
Karateka is a poor example of Parallax on C64, as it apparently does (slow) bitmap scrolling in front of a static background.
Parallax on the C64 tends to rely on the ability to redefine the character set and effectively use it as a tile set. You can smooth scroll characters using the graphics chip, so you only need to move them every 8 pixels.
Combine that with multiple character sets and you get a variation of the Duke Nukem II approach for "free" - you scroll the characters for the background with the foreground, but you flip to a partially scrolled definition of the tiles.
Another approach often used when the background is limited in complexity, is sprites.
A third option is banding. E.g. if the background you want to parallax scroll is above the normal play area, you can use the raster interrupt to control the scrolling independently for each band.
A fourth option is a bitmap scroll of the tile data. This is "easy" if your parallax bands are limited patterns. E.g. you might fill one band of the background with 0123012301230123 over and over, and then just scroll that as a 32 bit pattern in the character definition.
In any case, the key to all of these is that few c64 games use the bitmap mode (a few do), and so you get to offset the slow CPU with moving far less data around. Tack on the hardware sprites and raster interrupt and you can do a lot of interesting stuff.
Here's a great page on Parallax in C64 games with some video:
I've read the technical explanation but it was beyond me at time.