Sure you need to restart.? Usually, as soon as you drag your favorite language to the top, the next app you fire up should already reflect this change. So you might be running e.g. Mail in spanish and Safari in english concurrently.
For the Mac OS X to get running in the new language, a log out-log in, as S.H. pointed out, is in order.
Sure, you could restart (Force Quit) the Finder (command-option-esc), so you get the new language set without having to log out or restart the Mac, but that would only work for the Finder. Any other app, you should close it and open it again.