To understand prelinking you need to understand a little bit about linking

.
I am no expert in the field, but I can give a really high level overview of what's going on.
Basically, when you compile a program, there are some things that cannot be figured out at compile-time. For instance, the locations of dynamically linked libraries -- these must be figured out at runtime (otherwise, what's the point of dynamically linked libraries?). This certainly takes time, as hard drives are fairly slow and a good amount of information must be gathered.
Once all this information is gathered the linker performs bytecode manipulation of the entire program after it is loaded into memory but before it runs. The process could take a little more time for large binaries here as well.
So prelinking would almost be like a pseudo-static link. Perhaps a static link that could be removed. It might still be slower than static linking as the linker is still going to have to determine where the library is in memory (no way to determine that in advance, unlike disk location). But the advantage here is that the prelink can be removed, unlike static linking.
So basically a prelinker is taking as much load off the linker (and therefore the load-time) as possible. Please note, however, that prelinking or statically linking will not make a program any faster _after_ it has loaded.