Various methods.
---------------
Open your registry editor by typing 'regedit.exe' in the 'Run' command in the Start menu.
Find the key [HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Messenger]
Change the value of "Start" to "4" to disable the Messenger service.
Restart Windows for the change to take effect.
------------------
Windows 2000
Click Start-> Programs-> Administrative Tools->Services
Scroll down and highlight "Messenger"
Right-click the highlighted line and choose Properties.
Click the STOP button.
Select Disable or Manual in the Startup Type scroll bar
Click OK.
--------------------------
Windows XP
Click Start->Control Panel
Click Performance and Maintenance
Click Administrative Tools
Double click Services
Scroll down and highlight "Messenger"
Right-click the highlighted line and choose Properties.
Click the STOP button.
Select Disable or Manual in the Startup Type scroll bar
Click OK
------------------------
Windows NT
Click Start ->Control Panel
Double Click Administrative Tools
Select Services-> Double-click on Messenger
In the Messenger Properties window, select Stop,
Then choose Disable as the Startup Type
Click OK
------------------------
Windows 98 & ME
Windows Messenger Service cannot be disabled
(as far as I know)