Ah OK, it wasn't clear from your original post that you were referring to highlighted words.
This is part of Services, rather than Safari per se. It should work with any Cocao application like TextEdit for example. command
shiftL stills works when the text is highlighted in Safari 3 on Tiger.
In Leopard, if you go to Safari menu -> Services -> Search With Google what keyboard shortcut does it display there?