Draw on screen border in Commodore 64
Note that what Krestage 3 did (as mentioned in the question) is different.
One level of the trick is to mess with the border when the bottom of the "paper" (work-area rectangle, the thing inside the border) is just being drawn. This lets you have sprites in the upper and lower border.
A higher level is to mess with it at the right-hand edge of the paper, in every raster line, all as explained in JohnD's answer above. This lets you have sprites in the left and right border.
None of this lets you have more than 8 sprites in one line. That's just Krest magic.
By far the best resource (I know of) for the VIC chip is "The MOS 6567/6569 video controller (VIC-II) and its application in the Commodore 64" by Christian Bauer and a useful addendum is "The memory accesses of the MOS 6569 VIC-II and MOS 8566 VIC-IIe Video Interface Controller" by Marko Mäkelä.
Caveat lector: these are somewhat technical, and you might find them easier to understand after you've programmed some VIC effects yourself.
If the links ever die, just google up the articles by title, they're endlessly replicated.
Firstly only sprites can be displayed in the border area or a repeating 8 bit pattern (8 pixels wide) which is read from the last byte of the video bank, usually $3fff. Note you can only see these sprites or 8 bit pattern when you trick the VIC chip into "not displaying" the borders. See below.
The borders have a higher priority than sprites, so normally when a sprite is drawn in a border area the border covers the sprite. With a bit of VIC chip trickery you can turn the borders off.
You can turn the top and bottom borders off quite easily (I'll explain below), and the side borders off with very critical timing.
Firstly a little bit of info on how the VIC chip works on a c64.
The VIC chip draws the screen from the top left to the top right, then down a line, and from left to right again until the entire screen is drawn. It performs this redraw 50 times a second (for PAL units) or 60 times a second for (NTSC units).
There is an 8-bit VIC register that contains the vertical position of the raster at any given time. $d012. Actually there are more than 255 possible positions, so the 9th bit is stored in bit 7 (highest bit) or register $d011. So at any point you can read these registers and find out the vertical position of the raster. There is no available register to read the x position of the raster.
Another cool feature of the VIC chip was used to fix a problem when using hardware scrolling. Basic vertical scrolling was achieved by using a hardware register to move the screen 0-7 pixels vertically. Once you reached limit (0 or 7 depending on the direction of the scroll) you would move each character block (8x8 pixel) one block vertically and draw the new data to be displayed at the top (or bottom depending direction). This works very well, except that every 8 pixels of scrolling you would see data "pop" onto the screen. To remedy this, you could make the border area grow by 8 pixels vertically by clearing bit 3 in register $d011. This is called 24 row mode. By default the screen was set to 25 rows of 8x8 pixel characters. In 24 row mode, you could still draw characters to the bottom row, they would just be hidden by the border.
So the trick to turning off the top and bottom borders is to:
1) Set the screen to 25 row mode
2) wait for the raster to reach a vertical position between $f2 and $fa (the 8 pixels between where the border starts in both 24 row mode and 25 row mode).
3) Set the screen to 24 row mode... moving the vertical start of the border above the current raster position
4) Wait until after vertical raster position ($fa)
5) Repeat each frame
Step 3) tricks the VIC chip into thinking that it has already started drawing the border, so it never starts drawing it. Voila, the top and bottom borders are open.
Regarding side borders you can do the same thing with different registers, but as the horizontal movement of the raster is a lot quicker than the vertical movement, the timing needs to be much tighter. And there is another issue to take into account called jitter. <-which I won't explain here. Search the web for "Stable Raster C64" for an in depth explanation of that issue.