As far as I know, you can only do that in Windows 2000 and above... but any relatively new system would have that (unless you're running *gasp* Linux. Or something. You weirdo.
).
And yes, I believe that method keeps the priority you set after you reboot.
Dilbert: If you need a little step-by-step, what you do is this. Toss up a little CTRL-ALT-DEL action, then go to task manager. Make sure the program you want to set the priority for is running, and go to the processes tab, up at the top. Sort it by name by clicking the "Image Name" tab, then look for the name of the program (eg: Internet Explorer is "IEXPLORE.EXE"). Right click that, go to "Set Priority" down at the bottom, set your priority and BAM!
You're set.