1. Activate Ubuntu universe sources. The procedure is well-documented by Ubuntu.
2. use apt-get or synaptic to install prelink.
3. Open /etc/default/prelink with your favorite editor, as sudo/root.
4. Change PRELINKING=unknown from unknown to yes.
5. Adjust the other options if you know what the heck you're doing. Defaults work well.
6. To start the first prelink (the longest one!), run sudo /etc/cron.daily/prelink
In the future, prelink performs a quick prelink (a less-than-1-minute procedure on most systems) daily, usually at midnight. Every 14 days, or whatever you changed it to be, a full prelink will run.
If you just did a major apt-get upgrade that changed systemwide libraries (i.e. libc6, glibc, major gnome/X libs, etc etc etc) and experience cryptic errors about libs, rerun step 6.
To undo prelink, change step 4 from yes to no, then rerun step 6.
