Look for a new icon in your notification area (bottom right; by the clock). It usually looks like a grey disk with teh tubes underneath. If you hover your mouse over it, you will see 'Windows Live Messenger'. If you still can't spot it, here's how it should look like:
http://tinypic.com/4gdm8ol.png - Double clicky to bring your Messenger back.